Page 1 of 1

### 10864 - The Predator

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

Posted: 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``````

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

Posted: 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.