Page 1 of 1

11601 - Avoiding Overlaps

Posted: Wed Apr 08, 2009 11:52 am
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;
}``````

Re: 11601 WA

Posted: Sat Apr 11, 2009 2:22 pm
try this,
input:

Code: Select all

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

Code: Select all

``````Case 1: 1
``````

Re: 11601 WA

Posted: Sun Apr 12, 2009 10:05 am
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.

Re: 11601 WA

Posted: Thu Apr 16, 2009 7:02 pm
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
``````

Re: 11601 WA

Posted: Wed Apr 22, 2009 7:58 pm
I use O(n^2)algo and got TLE, please tell me why? I think that this algo should work ok...

Re: 11601 WA

Posted: Sun Apr 26, 2009 8:21 am
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.

Re: 11601 WA

Posted: Sun Apr 26, 2009 7:23 pm
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.

Re: 11601 WA

Posted: Mon May 04, 2009 7:14 pm
What algo do you use??????

Re: 11601 - Avoiding Overlaps

Posted: Wed May 20, 2009 7:55 pm
Somebody please tell me what is a complexity of your algo(accepted )???

Re: 11601 - Avoiding Overlaps

Posted: Fri May 22, 2009 12:32 am
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.

Re: 11601 - Avoiding Overlaps

Posted: Sun Nov 07, 2010 2:53 pm
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)

Re: 11601 - Avoiding Overlaps

Posted: Thu Dec 27, 2018 4:17 pm
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;
}
``````