OJ Board

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

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

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