Cod sursa(job #927979)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 26 martie 2013 10:14:53
Problema Oypara Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include<fstream>
#include<algorithm>
#include<string.h>
 
using namespace std;
 
#define max_n 100010
#define inf 2000000000
 
ifstream f("oypara.in");
ofstream g("oypara.out");
 
struct punct{
    int x , y;
}P1[max_n] , P2[max_n];
 
int n , x , y10 , y2 , k1 , k2 , semn1 , semn2 , s1 , p1 , p2;
int Fig1[max_n] , Fig2[max_n];
 
void read(){
     
    f>>n;
     
    for(int i = 1; i<= n ; i++){
        f>>x>>y10>>y2;
        if(y10>y2) swap(y10 , y2);
        P1[i].x = x; P1[i].y = y10;
        P2[i].x = x; P2[i].y = y2;
    }
     
}
 
int cmp(punct a , punct b){
    return a.y * b.x < a.x * b.y;
}
 
void reduce(punct P[] ,int &x_min ,int &y_min){
    int minim = inf , p_min;
    for(int i = 1 ; i <= n ; i++){
        if( P[i].y < minim ){
            minim = P[i].y ; p_min = i;
        }
        else if(P[i].y == minim && P[i].x < P[p_min].x)
            p_min = i;
    }
     
    x_min = P[p_min].x ; y_min = P[p_min].y;
     
    swap(P[p_min] , P[n]);
     
    for(int i = 1 ; i <= n ; i++){
        P[i].x -= x_min; P[i].y -= y_min;
    }
}
 
int det(punct a , punct b , punct c){
    int semn = ( b.x - a.x ) * ( c.y - a.y ) - ( c.x - a.x ) * ( b.y - a.y );
    if(semn<0) return 0;
    return 1;
}
 
void infasuratoare(punct P[] , int Fig[] , int &k){
     
    int x_min , y_min , u;
     
    reduce(P , x_min , y_min);
    sort(P+1 , P+n , cmp);
     
    Fig[1] = n; Fig[2] = 1 ; u = 2;
     
    for(int i = 2 ; i < n ; i++){
         
        while( u >= 2 && det( P[Fig[u]] , P[Fig[u-1]] , P[i] ) )
            u--;
         
        Fig[++u] = i;
         
    }
    k = u;
     
    for(int i = 1 ; i<=n ; i++){
        P[i].x += x_min; P[i].y += y_min;
    }
     
}
 
void solve(){
     
    int i;
     
    Fig1[0] = Fig1[k1] ; memcpy(Fig1+k1+1 , Fig1 + 1 , sizeof(int)*k1);
    Fig2[0] = Fig2[k2] ; memcpy(Fig2+k2+1 , Fig2 + 1 , sizeof(int)*k2);
     
    p1 = 1;
    for(i=2;i<=k1;i++){
        if(P1[Fig1[i]].x<P1[Fig1[p1]].x)
            p1 = i;
    }
     
    p1+=k1;
     
    p2 = 1;
    for(i=2;i<=k2;i++){
        if(P2[Fig2[i]].x>P1[Fig2[p2]].x)
            p2 = i;
    }
     
    while(true){
         
        do{
            semn1 = det(P1[Fig1[p1]] , P2[Fig2[p2]] , P2[Fig2[p2+1]]);
            semn2 = det(P1[Fig1[p1]] , P2[Fig2[p2]] , P2[Fig2[p2-1]]);
        }while(semn1!=semn2 && ( p2++ ));
         
        s1 = semn1;
         
        semn1 = det(P1[Fig1[p1]] , P2[Fig2[p2]] , P1[Fig1[p1+1]]);
        semn2 = det(P1[Fig1[p1]] , P2[Fig2[p2]] , P1[Fig1[p1-1]]);
         
        if(semn1==semn2){
            if(s1!=semn1){
                g<<P1[Fig1[p1]].x<<" "<<P1[Fig1[p1]].y<<" "<<P2[Fig2[p2]].x<<" "<<P2[Fig2[p2]].y<<"\n";
                break;
            }
        }
        p1--;
    }
     
}
 
int main(){
     
    read();
     
    infasuratoare(P1 , Fig1 , k1);
    infasuratoare(P2 , Fig2 , k2);
     
    solve();
     
    return 0;
}