## 11601 - Avoiding Overlaps

All about problems in Volume 116. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### 11601 - Avoiding Overlaps

Some 1 please help me. is there any thing missing??
Why m getting wa?

Code: Select all

``````#include<math.h>

int distance(int x1,int y1,int x2,int y2)
{
int d;
d = sqrt((y2-y1)*(y2-y1)+(x2-x1)*(x2-x1));
return d;
}

int main()
{
int t,n,x1,y1,x2,y2,c=0,i,j,overlap,length,width,area;
bool num[201][201];
scanf("%d",&t);
while(t--)
{
bool enter=0;
area=0;
for(i=0;i<201;i++)for(j=0;j<201;j++)num[i][j]=0;
scanf("%d",&n);
while(n--)
{
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
x1+=99;x2+=99;y1+=99;y2+=99;
if(!enter)
{
length = distance(x1,y1,x2,y1);
width = distance(x1,y1,x1,y2);
area = length*width;
for(i=x1;i<=x2;i++)
for(j=y1;j<=y2;j++)
num[i][j]=1;
enter=1;
}
else
{
overlap=0;
for(i=x1+1;i<x2;i++){for(j=y1+1;j<y2;j++){if(num[i][j]==1){overlap = 1;break;}}}
if(!overlap)
{
length = distance(x1,y1,x2,y1);
width = distance(x1,y1,x1,y2);
area += length*width;
for(i=x1;i<x2;i++)
for(j=y1;j<y2;j++)
num[i][j]=1;
}
}
}
c++;
printf("Case %d: %d\n",c,area);
}
return 0;
}``````
try_try_try_try_&&&_try@try.com
This may be the address of success.
shiplu_1320
New poster
Posts: 32
Joined: Sat Dec 29, 2007 9:08 pm
Location: CSEDU , Dhaka
Contact:

### Re: 11601 WA

try this,
input:

Code: Select all

``````1
2
0 0 1 1
0 0 1 1
``````
output:

Code: Select all

``````Case 1: 1
``````
A learner......
Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 11601 WA

I checked By this extra line and got right output 4 above case

Code: Select all

``if(num[x1][y1]==1&&num[x1][y2]==1&&num[x2][y1]==1&&num[x2][y2]==1)overlap=1;``
And still got Wa.
For this case my output is:
Input

Code: Select all

``````1
2
0 0 1 1
-1 -1 2 2``````
Output:

Code: Select all

``Case 1: 1``
I think i need more case.
try_try_try_try_&&&_try@try.com
This may be the address of success.
Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11601 WA

Try such tests:

Code: Select all

``````13
3
0 0 1 1
2 0 3 1
1 0 2 1
3
0 0 1 1
2 2 3 3
1 1 2 2
3
-1 -1 1 1
0 0 10 10
1 0 2 2
2
0 0 1 1
0 0 1 1
2
0 0 1 1
0 0 10 10
2
0 0 10 10
0 0 1 1
0
3
0 0 2 2
0 4 2 7
0 2 2 4
5
0 0 1 1
0 2 1 3
2 0 3 1
2 2 3 3
1 1 2 2
9
0 0 1 1
0 2 1 3
2 0 3 1
2 2 3 3
1 1 2 2
0 1 1 2
1 2 2 3
2 1 3 2
1 0 2 1
5
0 0 5 5
0 0 1 1
0 4 1 5
4 0 5 1
4 4 5 5
11
0 0 5 5
0 0 1 1
0 4 1 5
4 0 5 1
4 4 5 5
0 5 1 6
5 5 6 6
-1 4 0 5
-1 5 0 6
4 -1 5 0
-1 -1 0 0
8
0 0 1 10
2 0 3 9
2 9 3 10
1 1 2 2
1 3 2 4
1 2 2 3
1 0 2 10
1 0 2 2
``````

Code: Select all

``````Case 1: 3
Case 2: 3
Case 3: 6
Case 4: 1
Case 5: 1
Case 6: 100
Case 7: 0
Case 8: 14
Case 9: 5
Case 10: 9
Case 11: 25
Case 12: 31
Case 13: 23
``````
Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11601 WA

I use O(n^2)algo and got TLE, please tell me why? I think that this algo should work ok...
Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 11601 WA

In the contest time when i used O(n^2) i got TLE. I think this approach should get TLE.
Becaues if we search O(n^2) time for every single point then remember how much time it takes.
try_try_try_try_&&&_try@try.com
This may be the address of success.
Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11601 WA

I think that 5 sec is gived for a one test case,so if max n=10000, n^2=100 000 000 , it should run about 1 sec.
Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11601 WA

What algo do you use??????
Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11601 - Avoiding Overlaps

Somebody please tell me what is a complexity of your algo(accepted )???
Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

### Re: 11601 - Avoiding Overlaps

Igor9669 wrote:Somebody please tell me what is a complexity of your algo(accepted )???
If I remember correctly in the wost case: my algorithm runs in time about 0.5*200^3+N*200 per testcase.
You can try also a 2 dimensional binary tree, I've used another method. And here I think that the 2D binary tree is slow.
zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: 11601 - Avoiding Overlaps

I used quad tree (I am not sure about the name, its a segment tree which works on 2D grid).
complexity is n log (200x200)
You should not always say what you know, but you should always know what you say.
metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 11601 - Avoiding Overlaps

Test data generator.

Code: Select all

``````#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[])
{
srand(time(NULL));
int T = 100;
cout << T << '\n';
for (int cs = 1; cs <= T; cs++)
{
int N = 1000;
cout << N << '\n';
for (int i = 0; i < N; i++)
{
int x1 = rand() % 198 - 99, x2 = rand() % 198 - 99;
if (x1 > x2) swap(x1, x2);
if (x1 == x2) x2++;
int y1 = rand() % 198 - 99, y2 = rand() % 198 - 99;
if (y1 > y2) swap(y1, y2);
if (y1 == y2) y2++;
cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
}
}

return 0;
}
``````