codeforces 260 E Dividing Kingdom (함수 식 선분 트 리)

제목 링크: http://codeforces.com/problemset/problem/260/E
제목: 2 차원 평면 에 있 는 점 을 제시 하고 네 개의 선 을 그 려 라. 두 개의 평행 은 X 축 두 개의 평행 은 Y 축 에 있 고 평면 을 9 개 로 나 누 어 각 조각의 점 개 수 를 주어진 9 개 수로 한다.
사고방식: Y 좌표 에 따라 선분 수 를 만든다.9 개의 위 치 를 매 거 하여 타당 성 을 판단 하 다.

#include <iostream>

#include <cstdio>

#include <string.h>

#include <algorithm>

using namespace std;



struct node

{

    int a,b,L,R,s,mid;

};



const int INF=1000000000;

const int M=100005;

node t[M<<6];

int root[M],tot;

int n,q[M];



struct point

{

    int x,y;

};



point p[M];



int cmp(point a,point b)

{

    if(a.x!=b.x) return a.x<b.x;

    return a.y<b.y;

}



int find(int low,int high,int p[],int key)

{

    int mid;

    while(low<=high)

    {

        mid=(low+high)>>1;

        if(p[mid]==key) break;

        if(p[mid]>key) high=mid-1;

        else low=mid+1;

    }

    return mid;

}



int build(int a,int b)

{

    int k=++tot;

    t[k].a=a;

    t[k].b=b;

    t[k].s=0;

    t[k].mid=(a+b)/2;

    if(a!=b)

    {

        t[k].L=build(a,t[k].mid);

        t[k].R=build(t[k].mid+1,b);

    }

    return k;

}



int change(int p,int x,int s)

{

    int k=++tot;

    t[k]=t[p];

    t[k].s+=s;

    if(t[k].a==x&&t[k].b==x) return k;

    if(x<=t[k].mid) t[k].L=change(t[p].L,x,s);

    else t[k].R=change(t[p].R,x,s);

    return k;

}



int query(int p,int q,int k)

{

    if(t[q].a==t[q].b) return t[q].a;

    int x=t[t[q].L].s-t[t[p].L].s;

    if(k<=x) return query(t[p].L,t[q].L,k);

    return query(t[p].R,t[q].R,k-x);

}



int data[9],visit[9],S[9];





int getKth(int L,int R,int k)

{

    return query(root[L],root[R],k);

}



int OK()

{

    int Left=S[0]+S[1]+S[2];

    int Mid=Left+S[3]+S[4]+S[5];

    if(p[Left-1].x==p[Left].x||p[Mid-1].x==p[Mid].x) return 0;



    int L0=-INF,R0=INF;

    L0=max(L0,getKth(0,Left,S[0]));

    R0=min(R0,getKth(0,Left,S[0]+1));

    if(R0-L0<1) return 0;

    L0=max(L0,getKth(Left,Mid,S[3]));

    R0=min(R0,getKth(Left,Mid,S[3]+1));

    if(R0-L0<1) return 0;

    L0=max(L0,getKth(Mid,n,S[6]));

    R0=min(R0,getKth(Mid,n,S[6]+1));

    if(R0-L0<1) return 0;



    int L1=-INF,R1=INF;

    L1=max(L1,getKth(0,Left,S[0]+S[1]));

    R1=min(R1,getKth(0,Left,S[0]+S[1]+1));

    if(R1-L1<1) return 0;

    L1=max(L1,getKth(Left,Mid,S[3]+S[4]));

    R1=min(R1,getKth(Left,Mid,S[3]+S[4]+1));

    if(R1-L1<1) return 0;

    L1=max(L1,getKth(Mid,n,S[6]+S[7]));

    R1=min(R1,getKth(Mid,n,S[6]+S[7]+1));

    if(R1-L1<1) return 0;



    int x1=(p[Left-1].x+p[Left].x)/2;

    int x2=(p[Mid-1].x+p[Mid].x)/2;

    int y1=(q[L0]+q[R0])/2;

    int y2=(q[L1]+q[R1])/2;

    printf("%d.5 %d.5
",x1,x2);

    printf("%d.5 %d.5
",y1,y2);

    return 1;

}



int DFS(int dep)

{

    if(dep==9) return OK();

    int i;

    for(i=0;i<9;i++) if(!visit[i])

    {

        visit[i]=1;

        S[dep]=data[i];

        if(DFS(dep+1)) return 1;

        visit[i]=0;

    }

    return 0;

}



int main()

{

    while(scanf("%d",&n)!=-1)

    {

        tot=0;

        int i,k;

        for(i=0;i<n;i++)

        {

            scanf("%d%d",&p[i].x,&p[i].y);

            q[i]=p[i].y;

        }

        sort(p,p+n,cmp);

        sort(q,q+n);

        k=unique(q,q+n)-q;

        for(i=0;i<n;i++) p[i].y=find(0,k-1,q,p[i].y);

        root[0]=build(0,k-1);

        for(i=0;i<n;i++) root[i+1]=change(root[i],p[i].y,1);

        for(i=0;i<9;i++) scanf("%d",data+i);

        memset(visit,0,sizeof(visit));

        if(!DFS(0)) puts("-1");

    }

    return 0;

}