Cod sursa(job #1479529)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 31 august 2015 16:01:02
Problema Oypara Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct segment{int x,y1,y2;};
segment segm[100010];
struct punct{int x,y;};
punct up[100010],down[100010],aux;
int up_size=2,down_size=2,n;
bool cmp(segment a,segment b){
    if(a.x<b.x)
        return true;
    return false;
}
long long det(punct a,punct b,punct c){
    return (long long) 1LL*a.x*b.y+1LL*b.x*c.y+1LL*c.x*a.y-1LL*a.x*c.y-1LL*b.x*a.y-1LL*c.x*b.y;
}
void upper_convex_hull(){
    int i;
    up[1].x=segm[1].x;
    up[1].y=segm[1].y2;
    up[2].x=segm[2].x;
    up[2].y=segm[2].y2;
    for(i=3;i<=n;i++){
        aux.x=segm[i].x;
        aux.y=segm[i].y2;
        while(det(up[up_size-1],up[up_size],aux)<0&&up_size>1)
            up_size--;
        up_size++;
        up[up_size]=aux;
    }
}
void lower_convex_hull(){
    int i;
    down[1].x=segm[1].x;
    down[1].y=segm[1].y1;
    down[2].x=segm[2].x;
    down[2].y=segm[2].y1;
    for(i=3;i<=n;i++){
        aux.x=segm[i].x;
        aux.y=segm[i].y1;
        while(det(down[down_size-1],down[down_size],aux)>0&&down_size>1)
            down_size--;
        down_size++;
        down[down_size]=aux;
    }
}
int intersect(punct a,punct b,punct c,punct d){
    long long m1,m2;
    m1=det(a,c,b);
    m2=det(a,d,b);
    if((m1<0&&m2>0)||(m1>0&&m2<0))
        return 1;
    return 0;
}
int main(){
    freopen("oypara.in","r",stdin);
    freopen("oypara.out","w",stdout);
    int i,j=1,nr;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d%d",&segm[i].x,&segm[i].y1,&segm[i].y2);
    sort(segm+1,segm+n+1,cmp);
    upper_convex_hull();
    lower_convex_hull();
    for(i=1;i<up_size;i++){
        nr=0;
        while(nr<=n){
            nr++;
            if(j<down_size){
                if(intersect(up[i],up[i+1],down[j],down[j+1])==1)
                    break;
            }
            else
                if(intersect(up[i],up[i+1],down[j],down[1])==1)
                    break;
            j++;
            if(j==down_size+1)
                j=1;
        }
        if(nr==n+1){
            printf("%d %d %d %d",up[i].x,up[i].y,up[i+1].x,up[i+1].y);
            return 0;
        }
    }
    return 0;
}