題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5128

題意：給出N個點，由這些點構(gòu)成兩個矩形，矩形是平行于x軸的，而且不能相交不能相鄰（共用同一邊），如果存在就輸出面積和否則輸出imp

思路：

這里要注意的是，如果長寬知道的情況下可以通過一個角落的點確定一個矩形，如果不知道長寬，一個對角線確定一個矩形；

這題有個比較坑的地方就是包含的情況，如果兩個矩形包含是合法的，面積為最大的那個；

#include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <cstdlib> #include <algorithm>using namespace std;struct Node {int x, y; } p[40];int have[210][210];int check (Node i, Node j, Node k, Node L) {int Left = min (k.x, L.x), Right = max (k.x, L.x);int down = min (k.y, L.y), up = max (k.y, L.y);if (Left > max (i.x, j.x)) return 1;else if (Right < min (i.x, j.x)) return 1;else if (up < min (i.y, j.y)) return 1;else if (down > max (i.y, j.y)) return 1;else if (min (i.x, j.x) < Left && max (i.x, j.x) > Right && // 兩個矩形包含的情況 返回 2 min (i.y, j.y) < down && max (i.y, j.y) > up) return 2;else if (min (i.x, j.x) > Left && max (i.x, j.x) < Right && min (i.y, j.y) > down && max (i.y, j.y) < up) return 2;else return 0; // 返回0說明不符合條件 }int main (void) {int N;while (scanf ("%d", &N) != EOF) {if (!N) break;memset (have, 0, sizeof (have));for (int i = 1; i <= N; ++i) scanf ("%d%d", &p[i].x, &p[i].y),have[p[i].x][p[i].y] = i;int ans = 0, tmp;for (int i = 1; i <= N; ++i) {for (int j = i+1; j <= N; ++j) { // 選對角線的第二個點的時候要注意不能選和第一點同x或者同y的點 if (p[i].x == p[j].x || p[i].y == p[j].y || // 用have存x，y對應(yīng)的p下標，如果是0，則不存在 !have[p[i].x][p[j].y] || !have[p[j].x][p[i].y]) continue;tmp = abs (p[i].x-p[j].x)*abs (p[i].y-p[j].y);for (int k = 1; k <= N; ++k) { // 第一個矩形選好后第二個矩形的第一個對角線的點要跳過第一個矩形的四個點 if (k == i || k == j || k == have[p[i].x][p[j].y] || k == have[p[j].x][p[i].y]) continue;for (int L = 1; L <= N; ++L) { int od = check (p[i], p[j], p[k], p[L]); // 判斷兩個矩形是否合法 if (L == k || L == i || L == j || p[k].x == p[L].x || p[k].y == p[L].y ||L == have[p[i].x][p[j].y] || L == have[p[j].x][p[i].y] ||!have[p[k].x][p[L].y] || !have[p[L].x][p[k].y] || !od) continue;int index = abs (p[k].x-p[L].x)*abs (p[k].y-p[L].y);if (od == 2) ans = max (ans, max (tmp, index));else ans = max (tmp+index, ans);}}} }if (ans == 0) printf ("imp\n");else printf ("%d\n", ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU 5128 The E-pang Palace 【暴力】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。