Cod sursa(job #1816643)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 26 noiembrie 2016 18:11:16
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define N 120010
#define e 0.000000000001

using namespace std;

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

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[stp], 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 < 0  || 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 ];
    int sp = 1;
    for ( i = 2 ; i <  n ; i++ ){
        while (  sp >=2  && sgn ( stk [sp-1] , stk[sp] , v[i]) < 0 ){
            sp--;
        }
        stk[++sp] = v[i];
    }

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

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

    return 0;
}