Cod sursa(job #2370025)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 6 martie 2019 10:21:46
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;

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

struct point
{
    long double x, y;
}p[120005];

int n, k;
int sol[120005];

long double det(point a, point b, point c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
}

bool cmp(point &a, point &b)
{
    return det(a, b, p[1])<0;
}

int main()
{
    fin>>n;
    fin>>p[1].x>>p[1].y;
    for(int i=2; i<=n; ++i)
    {
        fin>>p[i].x>>p[i].y;
        if(p[i].x<p[1].x)
        {
            swap(p[1], p[i]);
            continue;
        }
        if(p[i].x==p[1].x && p[i].y<p[1].y)
        {
            swap(p[1], p[i]);
            continue;
        }
    }
    sort(p+2, p+n+1, cmp);
    k=0;
    sol[++k]=1;
    for(int i=2; i<=n; ++i)
    {
        while(k>=2 && det(p[sol[k-1]], p[sol[k]], p[i])>0) --k;
        sol[++k]=i;
    }
    fout<<k<<"\n";
    for(int i=k; i>=1; --i)
    {
        fout<<fixed<<setprecision(6)<<p[sol[i]].x<<" "<<p[sol[i]].y<<"\n";
    }
    return 0;
}