2017.07.12【NOIP提高组】模拟赛B组 Super B

原题：

http://172.16.0.132/senior/#contest/show/2049/0

题目描述：

“我是超级大沙茶”——Mato_No1
为了证明自己是一个超级大沙茶，Mato 神犇决定展示自己对叉（十字型）有多么的了解。
Mato 神犇有一个平面直角坐标系，上面有一些线段，保证这些线段至少与一条坐标轴平行。Mato 神犇需要指出，这些线段构成的最大的十字型有多大。
称一个图形为大小为R（R 为正整数）的十字型，当且仅当，这个图形具有一个中心点，它存在于某一条线段上，并且由该点向上下左右延伸出的长度为R 的线段都被已有的线段覆盖。
你可以假定：没有两条共线的线段具有公共点，没有重合的线段。

输入：

第一行，一个正整数N，代表线段的数目。
以下N 行，每行四个整数x1,y1,x2,y2（x1=x2 或y1=y2），描述了一条线段。

输出：

当不存在十字型时：输出一行“Human intelligence is really terrible”（不包括引号）。
否则：输出一行，一个整数，为最大的R。

样例输入：

输入1：
1
0 0 0 1
输入2：
3
-1 0 5 0
0 -1 0 1
2 -2 2 2

样例输出：

输出1：
Human intelligence is really terrible
输出2：
2

数据范围限制：

对于50%的数据：N≤1000。
对于100%的数据：1≤N≤100000，所有坐标的范围在-10^9~109 中。
后50%内，所有数据均为随机生成。

分析：

暴力+优化
将⊥x轴和⊥y轴的先分开存，快排取长度最长的5000个（别问我怎么得到的，卡常！！！）
再暴力枚举O(n^2)判断两条线有没有相交，取四头到交点的最小值，更新ans最大值

实现：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int ans=-1,n,i,j,a,b,c,d,ta,tb,aa[100001][6],bb[100001][6];
void qa(int l,int r)
{
    int i=l,j=r,mid=aa[(l+r)/2][5];
    do
    {
        while(aa[i][5]>mid) i++;
        while(aa[j][5]<mid) j--;
        if(i<=j)
        {
            memcpy(aa[0],aa[i],sizeof(aa[i]));
            memcpy(aa[i],aa[j],sizeof(aa[j]));
            memcpy(aa[j],aa[0],sizeof(aa[0]));
            i++;
            j--;
        }
    }
    while(i<=j);
    if(i<r) qa(i,r);
    if(l<j) qa(l,j);
}
void qb(int l,int r)
{
    int i=l,j=r,mid=bb[(l+r)/2][5];
    do
    {
        while(bb[i][5]>mid) i++;
        while(bb[j][5]<mid) j--;
        if(i<=j)
        {
            memcpy(bb[0],bb[i],sizeof(bb[i]));
            memcpy(bb[i],bb[j],sizeof(bb[j]));
            memcpy(bb[j],bb[0],sizeof(bb[0]));
            i++;
            j--;
        }
    }
    while(i<=j);
    if(i<r) qb(i,r);
    if(l<j) qb(l,j);
}
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        if(b==d)
        {
            aa[++ta][1]=a;
            aa[ta][2]=b;
            aa[ta][3]=c;
            aa[ta][4]=d;
            if(a>c)
            {
                swap(aa[ta][1],aa[ta][3]);
                swap(aa[ta][2],aa[ta][4]);
            }
            aa[ta][5]=aa[ta][3]-aa[ta][1];
        }
        if(a==c)
        {
            bb[++tb][1]=a;
            bb[tb][2]=b;
            bb[tb][3]=c;
            bb[tb][4]=d;
            if(b>d)
            {
                swap(bb[tb][1],bb[tb][3]);
                swap(bb[tb][2],bb[tb][4]);
            }
            bb[tb][5]=bb[tb][4]-bb[tb][2];
        }
    }
    qa(1,ta);
    qb(1,tb);
    for(i=1;i<=ta;i++)
    {
        if(aa[i][5]<=ans*2) break;
        for(j=1;j<=tb;j++)
        {
            if(bb[i][5]<=ans*2) break;
            if(bb[j][2]<aa[i][2] && aa[i][2]<bb[j][4] && aa[i][1]<bb[j][1] && bb[j][1]<aa[i][3])
                ans=max( ans,min( min( bb[j][1]-aa[i][1],aa[i][3]-bb[j][1] ),min( aa[i][2]-bb[j][2],bb[j][4]-aa[i][2] ) ) );
        }
    }
    if(ans==-1) printf("Human intelligence is really terrible");
    else printf("%d",ans);
}