Cod sursa(job #2090895)

Utilizator Victor24Vasiesiu Victor Victor24 Data 18 decembrie 2017 20:21:29
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

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

double sarrus( pair<double,double> a, pair<double,double> b, pair<double,double> c )
{
    return ( a.x*b.y + b.x*c.y + c.x*a.y ) - ( a.y*b.x + b.y*c.x + c.y*a.x );
}

int n, i, top = 2, ind = top;

double dx, dy;

pair < double, double > v[120005], st[120005];

int main()
{

    f>>n;

    for ( i = 1; i <= n; i++ )
    {
        f>>dx>>dy;

        v[i] = { dx, dy };

    }

    sort ( v + 1 , v + n + 1 );

    st[1] = v[1];
    st[2] = v[2];

    for ( i = 3; i <= n; i++ )
    {
        while ( top >= 2 )
        {
            if ( sarrus( st[top-1], v[i] , st[top] ) < 0 )
            {
                top--;
            }
            else
            {
                break;
            }
        }
        st[++top] = v[i];
    }

    ind = top;

    for ( i = n-1; i >= 1; i-- )
    {
        while ( top - ind >= 1 )
        {
            if ( sarrus( st[top-1], v[i] , st[top] ) < 0 )
            {
                top--;
            }
            else
            {
                break;
            }
        }
        st[++top] = v[i];
    }

    g<<top-1<<'\n';

    for ( i = top-1 ; i >= 1 ; i-- )
    {
        g<<setprecision(6) << fixed << st[i].x << " "<< st[i].y<<'\n';
    }

    return 0;
}