Cod sursa(job #1567942)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 13 ianuarie 2016 20:26:17
Problema Oypara Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=110000;
const int INF=200000000;
class Point{
    public:
        int x,y;
        Point(){
        }
        Point(int _x,int _y){
            x=_x;
            y=_y;
        }
};
class Segment{
    public:
        int x,y1,y2;
        Segment(){
        }
        Segment(int _x,int _y1,int _y2){
            x=_x;
            y1=_y1;
            y2=_y2;
        }
        bool operator<(const Segment&s)const{
            return x<s.x;
        }

};
Point up[N+1];
Point down[N+1];
Segment v[N+1];
Segment u[N+1];
int n,nup,ndown;
long long det(Point p1,Point p2,Point p3){
    return 1LL*p1.x*p2.y+
           1LL*p2.x*p3.y+
           1LL*p3.x*p1.y-(
           1LL*p2.y*p3.x+
           1LL*p3.y*p1.x+
           1LL*p1.y*p2.x);
}
Segment intersection(Segment s1,Segment s2){
    return Segment(s1.x,max(s1.y1,s2.y1),min(s1.y2,s2.y2));
}
Point pd(Segment s){
    return Point(s.x,s.y1);
}
Point pu(Segment s){
    return Point(s.x,s.y2);
}

void set_up(){
    up[1]=pu(v[1]);
    up[2]=pu(v[2]);
    nup=2;
    for(int i=3;i<=n;i++){
        while(nup>1&&det(up[nup-1],up[nup],pu(v[i]))<=0)
            nup--;
        up[++nup]=pu(v[i]);
    }
    up[nup+1]=Point(0,INF+1);
}
void set_down(){
    down[1]=pd(v[1]);
    down[2]=pd(v[2]);
    ndown=2;
    for(int i=3;i<=n;i++){
        while(ndown>1&&det(down[ndown-1],down[ndown],pd(v[i]))>=0)
            ndown--;
        down[++ndown]=pd(v[i]);
    }
}
int main(){
    freopen("oypara.in","r",stdin);
    freopen("oypara.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&v[i].x,&v[i].y1,&v[i].y2);
    sort(v+1,v+n+1);
    Segment _seg=Segment(0,0,0);
    int k=-1;
    for(int i=1;i<=n;i++)
        if(v[i].x!=v[i-1].x){
            u[++k]=_seg;
            _seg=v[i];
        }
        else
            _seg=intersection(_seg,v[i]);
    u[++k]=_seg;
    n=k;
    for(int i=1;i<=n;i++)
        v[i]=u[i];
    if(n==1){
        printf("%d %d %d %d",v[1].x,v[1].y1,v[1].x,v[1].y1+1);
        return 0;
    }
    set_up();
    set_down();
    int start=1;
    for(int i=1;i<n;i++){
        while(det(down[i],down[i+1],up[start])>=0){
            if(det(down[i],up[start],up[start+1])>=0){
                printf("%d %d %d %d",down[i].x,down[i].y,up[start].x,up[start].y);
                return 0;
            }
            start++;
        }
    }
    return 0;
}