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

本文主要是介绍【计算几何】POJ_1262 地板覆盖问题(Input)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

在一个$n\ast m$的地板里放$t$块砖。
如果有砖交叉覆盖，则输出$NONDISJOINT$
否则如果有砖超出了地板，则输出$NONCONTAINED$
否则如果有部分地板没有被覆盖，则输出$NONCOVERING$
否则输出$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();
}

这篇关于【计算几何】POJ_1262 地板覆盖问题(Input)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---