2017.07.12【NOIP向上組】模擬試合B組Super Big Stupid Cross問題解

原題:
http://172.16.0.132/senior/#contest/show/2049/0
タイトルの説明:
「私はスーパー大沙茶です」--Mato_No 1は自分がスーパー大沙茶であることを証明するために、Mato神はフォーク(十字型)に対する自分の理解を示すことにした.Mato神は平面直角座標系を持っていて、上にはいくつかの線分があり、これらの線分が少なくとも1つの座標軸と平行であることを保証しています.これらの線分で構成される最大の十字型がどれほど大きいかを指摘する必要がある.1つの図形をR(Rは正の整数)の大きさの十字型と呼び、かつ、この図形が中心点を有し、ある線分上に存在し、その点から上下左右に延びる長さRの線分が既存の線分で覆われている場合のみである.2つの共線のないセグメントに共通点があり、重なるセグメントがないと仮定できます.
入力:
1行目は、線分の数を表す正の整数Nである.以下のN行は、1行あたり4つの整数x 1,y 1,x 2,y 2(x 1=x 2またはy 1=y 2)の線分を記述する.
出力:
十字型が存在しない場合、「Human intelligence is really terrible」(引用符を除く)の行を出力します.それ以外の場合:1行、1つの整数を出力して、最大のRになります.
サンプル入力:
入力1:1 0 0 0 1入力2:3-1 0 5 0 0-1 0 1 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)は2本の線が交差しているかどうかを判断し、4頭から交点までの最小値を取り、ans最大値を更新する
実装:

#include
#include
#include
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) i++;
        while(bb[j][5]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]