Cod sursa(job #2736568)

Utilizator cdenisCovei Denis cdenis Data 3 aprilie 2021 17:14:41
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

typedef pair < double, double > Point;
#define x first
#define y second

Point v[120005],st[120005];
int n,pos=1,k=2;

inline int angle_cmp(Point a, Point b, Point c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

inline bool cmp(Point p1, Point p2)
{
    return angle_cmp(v[1],p1,p2)<0;
}

int main()
{
    fin >> n;
    for(int i=1;i<=n;i++)
        fin >> v[i].x >> v[i].y;
    for(int i=2;i<=n;i++)
        if(v[i]<v[pos])
            pos=i;
    swap(v[1],v[pos]);
    sort(v+2,v+n+1,cmp);
    st[1]=v[1];
    st[2]=v[2];
    for(int i=3;i<=n;i++)
    {
        while(k>=2 && angle_cmp(st[k-1],st[k],v[i])>0)
            k--;
        st[++k]=v[i];
    }
    fout << k << '\n';
    fout << fixed << setprecision(9);
    for(int i=k;i>=1;i--)
        fout << st[i].x << " " << st[i].y << '\n';
    return 0;
}