Cod sursa(job #1816933)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 27 noiembrie 2016 09:43:09
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define N 120110
#define e 0.000000000001

using namespace std;

struct point {
    double x , y ;
};
point v [ N ], stk [ N ];
int stp =-1 ;

int sgn ( point a , point b, point c ){
    return  ( b.x - a.x ) * ( c.y - a.y ) - ( c.x - a.x )*( b.y - a.y );
}

bool cmp ( point a , point b ){

    return sgn ( v[0], a ,b ) < 0;

}

double absd( double x ){
    if ( x < 0 ){
        return -x;
    }
    return x ;
}

int main(){
    int n ,i ;
    point t;

    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d",&n);

    for (i = 0 ; i < n ; i++ ){
        scanf("%lf %lf",&v[i].x , & v[i].y );
    }

    for (i = 0 ; i < n ; i++ ){
        if ( v[i].y < v[stp].y   || stp == -1 ){
            stp = i;
        }
        if ( absd (v[i].y - v[stp].y ) < e ){
            if( v[ i ].x - v[ stp ].x < 0 ){
                stp = i;
            }
        }

    }

    t = v [ stp ] ;
    v [ stp ] = v[ 0 ];
    v[ 0 ] = t ;

    sort( v +1 , v + n , cmp );


    stk [ 0 ] = v[ 0 ];
    stk [ 1 ] = v[ 1 ];
    stk [ 2 ] = v[ 2 ];
    int sp = 2;
    for ( i = 3 ; i <  n ; i++ ){
        while (  sp >=1  && sgn ( stk [sp-1] , stk[sp] , v[i]) > 0 ){
            sp--;
        }
        stk[++sp] = v[i];
    }

    printf("%d\n",sp+1);

    for ( i = sp ; i >=0  ; i-- ){
        printf("%lf %lf\n",stk[i].x , stk[i].y );
    }

    return 0;
}