10864 - The Predator

Moderator: Board moderators

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

10864 - The Predator

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;
{
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;
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.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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:
Thank you for test cases. They helped me to understand that my algorithm is wrong.

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 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.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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:
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.