Cod sursa(job #2406582)

Utilizator liviu2000Dragomirescu Liviu liviu2000 Data 15 aprilie 2019 21:48:36
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <bits/stdc++.h>
#define N 120005

using namespace std;

ifstream fin("infasuratoare.in") ;
ofstream fout("infusaratoare.out") ;

pair<double,double> pi , pct[N] ;
vector<pair<double,double> > vv;

bool cmp(pair<double,double> p1,pair<double,double> p2 )
{
    return ((p1.second-pi.second)*(p2.first-pi.first)<(p1.first-pi.first)*(p2.second-pi.second)) ;
}

int faria (pair<double,double> p1 , pair<double,double> p2 , pair<double,double> p3 )
{
    double aria = (p2.first-p1.first)*(p3.second-p1.second) - (p2.second-p1.second)*(p3.first-p1.first) ;
    if ( aria < 0 )
        return -1 ;
    if ( aria == 0 )
        return 0 ;
    return 1;
}

int main()
{
    double x , y , xmin , ymin = 1000000001 , ar;
    int i , n ,id;
    fin >> n ;
    for ( i = 1 ; i <= n ; i++ )
    {
        fin >> x >> y ;
        pct[i].first = x ;
        pct[i].second = y ;
        if ( y < ymin )
        {
            ymin = y ;
            xmin = x;
            pi.first = x ;
            pi.second = y ;
            id = i ;
        }
        if ( y == ymin )
        {
            if ( x < xmin )
            {
                x = xmin ;
                pi.first = x ;
                pi.second = y ;
                id = i ;
            }
        }
    }
    swap(pct[1],pct[id]) ;
    sort(pct+2,pct+n+1,cmp) ;
    vv.push_back(pct[1]) ;
    vv.push_back(pct[2]) ;
    for ( i = 3 ; i <= n ; i++ )
    {
        ar = faria(vv[vv.size()-2],vv[vv.size()-1],pct[i]);
        if ( ar > 0 )
            vv.push_back(pct[i]) ;
        if ( ar < 0 )
        {
            vv.pop_back() ;
            vv.push_back(pct[i]);
        }
    }
    for ( auto vec : vv )
        fout << setprecision(12) << vec.first << " " << vec.second << '\n' ;
}