Cod sursa(job #3216267)

Utilizator xDemonstyMatei Haba Ionut xDemonsty Data 15 martie 2024 19:30:43
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct point
{
    double x, y;
}v[200005];
int n ;
long double cross_product(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 (cross_product(v[1],a,b) < 0 ) ;

}

point stiva[20005];
int main()
{
    cin >> n ;
    long long ind = 0 ;
    long long miny , minx ;
    cin >> v[1].x >> v[1].y;
    miny = v[1].y;
     minx = v[1].x;
    for ( int i = 2 ; i <= n ; i ++ )
    {
        cin >> v[i].x >> v[i].y ;

        if ( v[i].x < minx)
        {
            minx = v[i].x;
            miny = v[i].y ;
            ind = i ;
        }
        else
            if ( v[i].x == minx )
        {
            if ( v[i].y < miny)
            {
                miny = v[i].y;
                ind = i ;
            }
        }
    }

    swap(v[ind],v[1]);
    sort(v+2,v+n+1,cmp);

    int head = 1 ;
    stiva[head] = v[1];
    stiva[head+1] = v[2];
    head ++ ;
    for( int i = 3 ; i <= n ; i ++ )
    {
        while ( head >= 2 && cross_product(stiva[head-1],stiva[head],v[i]) > 0 )
        {
            head -- ;
        }

        stiva[++head] = v[i];
    }

    cout << head << '\n';
    for ( int i = head ; i >= 1 ; i -- )
    {
        cout << fixed << setprecision(12) << stiva[i].x << " " << stiva[i].y << '\n';
    }



    return 0;
}