Cod sursa(job #1870460)

Utilizator alexandruchiriacAlexandru Chiriac alexandruchiriac Data 6 februarie 2017 17:44:35
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

#define x first
#define y second
#define punct pair < double , double >

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n , i , poz , nr;
pair < double, double > minn;
vector < pair < double , double > > v;
punct minnn;
punct st[120001];

double panta ( punct a, punct b , punct c )
{
    return ( b.x - a.x )*(c.y - a.y) - (b.y-a.y)*(c.x-a.x) ;
}

bool criteriu ( punct a, punct b )
{
    return panta(v[1],a,b)<0;
}


int main()
{
    f >> n;
    v = vector < pair < double , double > > (n+1);
    f >> v[1].x >> v[1].y;
    minn = v[1];
    for ( i = 2 ; i <= n ; i++ )
    {
        f >> v[i].x >> v[i].y;
        if ( minn.x > v[i].x or (minn.x==v[i].x and minn.y > v[i].y))
            minn = v[i] , poz = i;
    }
    swap(v[1],v[poz]);
    sort(v.begin()+2,v.end(),criteriu);

    st[1] = v[1];
    st[2] = v[2];
    nr = 2;
    for ( i = 3; i <= n ; i++ )
    {
       while( nr >=2 and panta(st[nr-1],st[nr],v[i]) > 0 )
       {
           --nr;
       }
       st[++nr] = v[i];
    }
    freopen("infasuratoare.out","w",stdout);
    printf( "%d\n", nr );
    for ( i = nr ; i >= 1 ; i-- )
    {
        printf( "%.9f %.9f\n" , st[i].x, st[i].y);
    }

    return 0;
}