Cod sursa(job #1671272)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 1 aprilie 2016 15:36:44
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#include <algorithm>
#define eps 0.000000

double X, Y;

struct puncte
{
    double x, y;
} p[120001], st[120001];

using namespace std;

bool cmp( puncte a, puncte b )
{
    return (a.y-Y)*(b.x-X)>(b.y-Y)*(a.x-X);
}
inline int verif( int i, int j )
{
    double a=(st[i].y-st[i-1].y)*(p[j].x-st[i-1].x);
    double b=(p[j].y-st[i-1].y)*(st[i].x-st[i-1].x);
    return a<b;
}

int main()
{
    freopen( "infasuratoare.in", "r", stdin );
    freopen( "infasuratoare.out", "w", stdout );
    int n, i, j, vf=0;
    scanf( "%d", &n );
    for( i=1;i<=n;i++ )
    {
        scanf( "%lf%lf", &p[i].x, &p[i].y );
        if( p[i].x<X )
            X=p[i].x, Y=p[i].y, j=i;
    }
    swap(p[1],p[j]);
    sort(p+2,p+n+1,cmp);
    for( i=1;i<=n;i++ )
    {
        while( vf>2 && verif(vf,i) )
            vf--;
        st[++vf]=p[i];
    }
    printf( "%d\n", vf );
    for( i=vf;i>=1;i-- )
        printf( "%.6lf %.6lf\n", st[i].x, st[i].y );
    return 0;
}