【计算几何】POJ_1262 地板覆盖问题(Input)

题意

在一个$n*m$n∗m的地板里放$t$t块砖。
如果有砖交叉覆盖，则输出$NONDISJOINT$NONDISJOINT
否则如果有砖超出了地板，则输出$NONCONTAINED$NONCONTAINED
否则如果有部分地板没有被覆盖，则输出$NONCOVERING$NONCOVERING
否则输出$OK$OK。

思路

这道题判断交叉比较关键，我们只要对它们的四个点进行判断就好了。

(r1.left<r2.right)&&(r2.left<r1.right)&&(r1.up<r2.down)&&(r2.up<r1.down)

剩下的部分直接判断即可。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>

struct node{
	int left, right, up, down;
}a[401];

int input() {
	char c = getchar();
	int f = 1, result = 0;
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		result = result * 10 + c - 48;
		c = getchar();
	}
	return result * f;
}

void solve() { 
	memset(a, 0, sizeof(a));
	int m = input(), n = input(), t = input();
	int s = n * m, sum = 0, over = 0;
	for (int i = 1; i <= t; i++) {
		a[i].left = input();
		a[i].up = input();
		a[i].right = input();
		a[i].down = input();
		if (a[i].up > a[i].down) std::swap(a[i].up, a[i].down);
		if (a[i].left > a[i].right) std::swap(a[i].left, a[i].right);
		sum += (a[i].down - a[i].up) * (a[i].right - a[i].left);
		if (a[i].left < 0 || a[i].left > m || a[i].up < 0 || a[i].up > n ||
			a[i].right < 0 || a[i].right > m || a[i].down < 0 || a[i].down > n)
				over = 1;
	}
	for (int i = 1; i <= t; i++)
		for (int j = i + 1; j <= t; j++) {
			if (a[i].left < a[j].right && a[j].left < a[i].right && a[i].up < a[j].down && a[j].up < a[i].down) {
				printf("NONDISJOINT\n");//判断交叉
				return;
			}
		}
	if (over) {//判断超出地板
		printf("NONCONTAINED\n");
		return;
	}
	else if (sum < s) {//判断没有被覆盖
		printf("NONCOVERING\n");
		return;
	}
	else printf("OK\n");
}

int main() {
	int q = input();
	for (; q; q--)
		solve();
}