原题：
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，所有坐标的范围在-109~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);
}
