11601 - Avoiding Overlaps

[Obaida]

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;
}

[shiplu_1320]

try this,
input:

Code: Select all

1
2
0 0 1 1
0 0 1 1

output:

Code: Select all

Case 1: 1

[Obaida]

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.

[Igor9669]

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

Answer:

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]

I use O(n^2)algo and got TLE, please tell me why? I think that this algo should work ok...

[Obaida]

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.

[Igor9669]

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]

What algo do you use??????

[Igor9669]

Somebody please tell me what is a complexity of your algo(accepted )???

[Robert Gerbicz]

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]

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)

[metaphysis]

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;
}