1592.cpp

来自「这是哈尔滨工业大学acmOJ的源代码」· C++ 代码 · 共 50 行

/*  This Code is Submitted by wywcgs for Problem 1592 on 2006-06-24 at 20:05:56 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int TN = 128;
const char R[][16] = { "NONDISJOINT", "NONCONTAINED", "NONCOVERING", "OK" };

class Tile {
public:
	int l, r, d, u;
	void make() { scanf("%d %d %d %d", &l, &d, &r, &u); }
	bool overlop(const Tile& t) const { return (l < t.r && r > t.l && d < t.u && u > t.d); }
	bool contain(int w, int h) const { return l >= 0 && r <= w && d >= 0 && u <= h; }
	int area() const { return (r-l)*(u-d); }
};

Tile tile[TN];
int n, w, h;

int check();

int main()
{
	int t, T, i;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d %d", &w, &h, &n);
		for(i = 0; i < n; i++) tile[i].make();
		printf("%s\n", R[check()]);
	}
	
	return 0;
}

int check()
{
	int i, j;
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			if(i != j && tile[i].overlop(tile[j])) return 0;
	int cover = 0;
	for(i = 0; i < n; i++) {
		if(!tile[i].contain(w, h)) return 1;
		cover += tile[i].area();
	}
	return (cover != w*h) ? 2 : 3;
}