众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
小葱同学现在抵挡咕星人的进攻。咕星人的进攻非常猛烈，以至于小葱同学不得不进行防守。为了更好地防守咕星人的进攻，小葱同学制作了??面盾牌，其中第??面盾牌的形状是左下角在(?? ?? ,?? ?? )右上角在(?? ?? ,?? ?? )的矩形。现在小葱将这??面盾牌组合在了一起，并且只有当这??面盾牌组成了一个漂亮的矩形时，小葱才能够抵挡咕星人的进攻。一个漂亮的矩形指的是盾牌不遗漏的覆盖了这个矩形内的每一个位置，并且每一个位置最多只被一个盾牌所覆盖（边界相交不算覆盖多次）。现在给定你这??面盾牌，你需要帮助小葱同学判断这??面盾牌是否组成了一个漂亮的矩形。
思路题，发现一个完美的矩形除了四个顶点可能会出现1个点，其他的地方都会出现2或4个点。
int a[MAXN], b[MAXN], c[MAXN], d[MAXN], flag, n, sum, MIN_X = INF, MIN_Y = INF, MAX_X = -INF, MAX_Y = -INF;; inline int min(int a, int b){return a < b ? a : b;} inline int max(int a, int b){return a > b ? a : b;} inline void C() { memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); memset(c, 0, sizeof(c)); memset(d, 0, sizeof(d)); flag = sum = 0; } map<int ,map<int, int> > k; inline void check(int i) { MIN_X = min(MIN_X, min(a[i], c[i])); MAX_X = max(MAX_X, max(a[i], c[i])); MIN_Y = min(MIN_Y, min(b[i], d[i])); MAX_Y = max(MAX_Y, max(b[i], d[i])); } inline int STD() { for (int i = 0; i <= n; i++) { check(i); sum += (c[i] - a[i]) * (b[i] - d[i]); } if (sum != (MAX_X - MIN_X) * (MAX_Y - MIN_Y)) return 0; int num = 0; for (int i = 1; i <= n; i++) { k[a[i]][b[i]]++; k[a[i]][d[i]]++; k[c[i]][b[i]]++; k[c[i]][d[i]]++; if (k[a[i]][b[i]] != 2 && k[a[i]][b[i]] != 4) num++; if (k[a[i]][d[i]] != 2 && k[a[i]][d[i]] != 4) num++; if (k[c[i]][b[i]] != 2 && k[c[i]][b[i]] != 4) num++; if (k[c[i]][d[i]] != 2 && k[c[i]][d[i]] != 4) num++; if (k[a[i]][b[i]] == 2 || k[a[i]][b[i]] == 4) num--; if (k[a[i]][d[i]] == 2 || k[a[i]][d[i]] == 4) num--; if (k[c[i]][b[i]] == 2 || k[c[i]][b[i]] == 4) num--; if (k[c[i]][d[i]] == 2 || k[c[i]][d[i]] == 4) num--; } return num == 4; } signed main() { // freopen("matrix.in", "r", stdin); // freopen("matrix.out", "w", stdout); int t = read(); while (t--) { C(); n = read(); for (int i = 1; i <= n; i++) a[i] = read(), b[i] = read(), c[i] = read(), d[i] = read(); if(STD()) puts("Perfect"); else puts("Guguwansui"); } return 0; }
原文：https://www.cnblogs.com/dead-gun/p/12990718.html
