Cod sursa(job #2284384)

Utilizator alexjircanalex jircan alexjircan Data 17 noiembrie 2018 10:48:19
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

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

pp p[120010];
int n, st[120010];

double determinant( pp a, pp b, pp c )
{
    double ans;
    ans = a.x*b.y + b.x*c.y + c.x*a.y - b.y*c.x - c.y*a.x - a.y*b.x;
    return ans;
}

int main()
{
    int i;
    fin >> n;
    for(i=1; i<=n; i++)
    {
        fin >> p[i].x >> p[i].y;
    }
    sort(p+1, p+n+1);
    st[1] = 1;
    st[2] = 2;
    st[0] = 2;
    for(i=3; i<=n; i++)
    {
        while( st[0]>1 &&  determinant( p[st[st[0]-1]], p[st[st[0]]], p[i] ) > 0 )
        {
            st[0]--;
        }
        st[ ++st[0] ] = i;
    }

    for(i=n-1; i>=1; i--)
    {
        while( determinant( p[st[st[0]-1]], p[st[st[0]]], p[i] ) > 0 )
        {
            st[0]--;
        }
        st[ ++st[0] ] = i;
    }

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