题目描述
“我是超级大沙茶”——Mato_No1为了证明自己是一个超级大沙茶,Mato 神犇决定展示自己对叉(十字型)有多么的了解。
Mato 神犇有一个平面直角坐标系,上面有一些线段,保证这些线段至少与一条坐标轴平行。Mato 神犇需要指出,这些线段构成的最大的十字型有多大。
称一个图形为大小为R(R 为正整数)的十字型,当且仅当,这个图形具有一个中心点,它存在于某一条线段上,并且由该点向上下左右延伸出的长度为R 的线段都被已有的线段覆盖。
你可以假定:没有两条共线的线段具有公共点,没有重合的线段。
思路
暴力判断将线段的长度从大到小排序
显然,若ans > len / 2 那么后面全部的线段都不会符合条件,所以直接break掉就可以了
#include#include using namespace std; #define maxn 100001 struct arr { int x1, y1, x2, y2, w; }a[maxn]; arr b[maxn]; int abs(int x) { if (x < 0) return -x; return x; } int cmp(arr a, arr b) { return a.w > b.w; } int minn(int a, int b, int c,int d) { int t = 0x7fffffff; if (a < t) t = a; if (b < t) t = b; if (c < t) t = c; if (d < t) t = d; return t; } int main() { int n; scanf("%d", &n); int l = 0, r = 0; for (int i = 1; i <= n; i++) { int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); if (x1 == x2) { int w = abs(y1 - y2); if (y1 > y2) {y1 ^= y2; y2 ^= y1; y1 ^= y2;} a[++l] = (arr) {x1, y1, x2, y2, w}; } else { int w = abs(x1 - x2); if (x1 > x2) {x1 ^= x2; x2 ^= x1; x1 ^= x2;} b[++r] = (arr) {x1, y1, x2, y2, w}; } } sort(a + 1, a + l + 1, cmp); sort(b + 1, b + r + 1, cmp); int ans = 0; for (int i = 1; i <= r; i++) { for (int j = 1; j <= l; j++) { if (a[j].w / 2 < ans) break; if (b[i].x1 < a[j].x1 && b[i].x2 > a[j].x2 && b[i].y1 > a[j].y1 && b[i].y2 < a[j].y2) { int x = a[j].x1, y = b[i].y1; int t = minn(a[j].y2 - y, y - a[j].y1, b[i].x2 - x, x - b[i].x1); ans = ans > t ? ans : t; } } if (b[i].w / 2 < ans) break; } if (ans == 0) printf("Human intelligence is really terrible\n"); else printf("%d\n", ans); }
Comments NOTHING