Cod sursa(job #938363)

Utilizator matei_cChristescu Matei matei_c Data 12 aprilie 2013 14:27:51
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std ;

#define maxn 120001
#define eps 0.000000000001

int n ;

pair<double, double> v[maxn] ;

bool sel[maxn] ;

int stiva[maxn], nr ;

int pas = 1 ;

int verifica(int x)
{
    if( x == n )
        pas = -pas ;

    return pas ;
}

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

    cin >> n ;

    for(int i = 1; i <= n; ++i )
        cin >> v[i].first >> v[i].second ;

}

double produs( pair<double, double> X, pair<double, double> A, pair<double, double> B )
{
    return ( A.first - X.first ) * ( B.second - X.second ) - ( B.first - X.first ) * ( A.second - X.second ) ;
}

void infasuratoare()
{
    sort( v + 1, v + n + 1 ) ;

    stiva[1] = 1 ;
    stiva[2] = 2 ;
    nr = 2 ;
    sel[2] = true ;

   for(int i = 1; i > 0; i += verifica(i) )
    {
        if( sel[i] )
            continue ;

        while( nr >= 2 && produs( v[ stiva[ nr - 1 ] ], v[ stiva[nr] ], v[i] ) < eps )
            sel[ stiva[ nr-- ] ] = false ;

        stiva[++nr] = i ;
        sel[i] = true ;
    }
}

void afisare()
{
    cout << nr - 1 << "\n" ;

    cout << setprecision(6) << fixed ;

    for(int i = 1; i < nr; ++i )
        cout << v[ stiva[i] ].first << " " << v[ stiva[i] ].second << "\n" ;
}

int main()
{
    citire() ;

    infasuratoare() ;

    afisare() ;

    return 0 ;
}