Page 1 of 1

10864 - The Predator

Posted: Wed Jun 08, 2005 7:28 pm
by Renat
Could anybody tell me what's wrong in my solution?

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <vector>
#include <string>

using namespace std;

#define For(i,a,b) for(int i=(a); i<=(b); i++)
#define Rep(i,n) for(int i=0; i<(n); i++)
#define Repd(i,n) for(int i=(n)-1; i>=0; i--)
#define Size(x) (int(x.size()))

struct rect
{
	int r1,c1,r2,c2;
	void read()
	{
		int k;
		scanf("%d%d%d",&r1,&c1,&k);
		r2=r1+k-1;
		c2=c1+k-1;
	}
	bool includes(int r,int c)
	{
		return r1<=r && r<=r2 && c1<=c && c<=c2;
	}
	int area()
	{
		return (r2-r1+1)*(c2-c1+1);
	}
	bool check()
	{
		return r1<=r2 && c1<=c2;
	}
};

bool inters(rect a,rect b,rect &c)
{
	c.r1=max(a.r1,b.r1);
	c.r2=min(a.r2,b.r2);
	c.c1=max(a.c1,b.c1);
	c.c2=min(a.c2,b.c2);
	return c.check();
}

vector<rect> rr;
int sum;

void rec(int k,int sg,rect cur)
{
	assert(cur.check());
	if(k<0) sum+=sg*cur.area();
	else
	{
		rec(k-1,sg,cur);
		rect r;
		if(inters(cur,rr[k],r)) rec(k-1,-sg,r);
	}
}

int solve(vector<rect> rs,int r,int c)
{
	rect big;
	big.r1=big.c1=1;
	big.r2=big.c2=10000;
	Repd(i,Size(rs)) if(rs[i].includes(r,c))
		assert(inters(big,rs[i],big));
	rr.clear();
	Repd(i,Size(rs)) if(!rs[i].includes(r,c))
	{
		rect r;
		if(inters(big,rs[i],r)) rr.push_back(r);
	}
	sum=0;
	rec(Size(rr)-1,1,big);
	return sum;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt","rt",stdin);
	freopen("output.txt","wt",stdout);
#endif

	int c,test;
	test=0;
	while(scanf("%d",&c)==1)
	{
		vector<rect> rs;
		For(i,1,c)
		{
			rect r;
			r.read();
			if(r.check()) rs.push_back(r);
		}
		scanf("%d",&c);
		printf("Case %d:\n",++test);
		For(i,1,c)
		{
			int r,c;
			scanf("%d%d",&r,&c);
			printf("%d\n",solve(rs,r,c));
		}
	}

	exit(0);
	return 0;
}
Thank you.

Posted: Fri Jun 10, 2005 8:41 am
by Cho
Your code couldn't be compiled in VC6. I didn't read it. (Debugging my own code is already painful enough. :-? )
Anyway, these are the test cases i created after I got my WA. Note that the input doesn't follow the spec, the value Q is greater than 5 in my input.
Input:

Code: Select all

4
2 3 8
3 2 8
4 4 9
9 9 6
59
1 1 1 2 1 3 2 1 2 2 3 1 3 11 11 3 8 13 13 8 8 15 15 8 15 15
2 3 2 10 3 10 3 2 10 2 10 3
3 3 3 9 9 3
4 4 4 9 9 4 8 8 8 9 9 8
4 10 10 4 8 10 10 8
9 9 9 10 10 9
4 11 4 12 8 11 8 12 11 4 12 4 11 8 12 8
12 12 9 12 12 9 9 11 11 9 10 10
9 13 9 14 13 9 14 9 10 13 10 14 13 10 14 10 13 13 14 14
4
2 3 1
3 2 1
3 4 1
4 3 1
9
2 2 2 3 2 4
3 2 3 3 3 4
4 2 4 3 4 4
3
3 2 2
2 4 3
5 3 2
41
3 2 4 2 3 3 4 3 5 3 6 3 5 4 6 4
2 4 3 4 4 4 2 5 3 5 4 5 2 6 3 6 4 6
2 3 2 2 2 1 3 1 4 1 5 1 5 2 6 2 7 2 7 3 7 4 7 5 6 5 5 5 5 6 5 7 4 7 3 7 2 7 1 7 1 6 1 5 1 4 1 3
4
2 2 1
2 2 1
2 2 1
2 2 1
9
1 1 1 2 1 3
2 1 2 2 2 3
3 1 3 2 3 3
Output:

Code: Select all

Case 1:
99999868 99999868 99999868 99999868 99999868 99999868 99999868
99999868 99999868 99999868 99999868 99999868 99999868
9 9 9 9 9 9
13 13 13
35 35 35 35 35 35
5 5 5 5
1 1 1
10 10 10 10 10 10 10 10
13 13 13 13 13 13
20 20 20 20 20 20 20 20 20 20
Case 2:
99999995 1 99999995 1 1 1 99999995 1 99999995
Case 3:
4 4 4 4 4 4 4 4
9 9 9 9 9 9 9 9 9
99999983 99999983 99999983 99999983 99999983 99999983 99999983 99999983
99999983 99999983 99999983 99999983 99999983 99999983 99999983 99999983
99999983 99999983 99999983 99999983 99999983 99999983 99999983 99999983
Case 4:
99999999 99999999 99999999 99999999 1 99999999 99999999 99999999 99999999

Posted: Fri Jun 10, 2005 11:34 am
by Renat
Thank you for test cases. They helped me to understand that my algorithm is wrong.

Posted: Tue Aug 16, 2005 4:56 pm
by Dreamer#1
Can someone please give me a good idea to solve this problem in a compact way? all I can think of is pretty complicated and I don't feel confident that they will be accepted.

Thanks in advance :)

Posted: Tue Aug 16, 2005 7:08 pm
by Cho
This is my approach:
By extending the eight vertical and horizontal line segments from the four given rectangles, the square region from (0,0) to (10000,10000) can be divided into 81 rectangular regions. The area of these regions are trivial to find out. Then, check all the adjacent regions to see if they are separated by a line segment. If not, merge their area. Finally, pick up the region of the query point and report its merged area.

Posted: Thu Aug 10, 2006 12:33 pm
by Moha
Can anybody post more test cases? I got WA. but I passed all of above testcases.
EDIT: I got it at last, Thank you Cho.