10864 - The Predator

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

Moderator: Board moderators

Post Reply
Renat
New poster
Posts: 10
Joined: Thu Jul 18, 2002 2:40 pm
Location: Russia
Contact:

10864 - The Predator

Post by Renat » Wed Jun 08, 2005 7:28 pm

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.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Fri Jun 10, 2005 8:41 am

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

Renat
New poster
Posts: 10
Joined: Thu Jul 18, 2002 2:40 pm
Location: Russia
Contact:

Post by Renat » Fri Jun 10, 2005 11:34 am

Thank you for test cases. They helped me to understand that my algorithm is wrong.

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Tue Aug 16, 2005 4:56 pm

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 :)

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Tue Aug 16, 2005 7:08 pm

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.

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Thu Aug 10, 2006 12:33 pm

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.

Post Reply

Return to “Volume 108 (10800-10899)”