题目描述

“我是超级大沙茶”——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);
}