Cod sursa(job #3296073)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 11 mai 2025 09:44:24
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
#define P pair<double,double>
#define x first
#define y second
const double E=1e-12;
P a[120001],b[120000];
double A(P a,P b,P c)
{
    return (a.x-b.x)*(c.y-b.y)-(a.y-b.y)*(c.x-b.x);
}
int main()
{
    int m=0,n;
    cin>>n;
    for(int i=1;i<=n;cin>>a[i].x>>a[i].y,++i);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;b[m++]=a[i++])
        for(;m>1&&A(b[m-2],b[m-1],a[i])<E;--m);
    for(int i=n-1,k=m;i;b[m++]=a[i--])
        for(;m>k&&A(b[m-2],b[m-1],a[i])<E;--m);
    for(--m,cout<<m<<'\n'<<fixed<<setprecision(6);m;--m,cout<<b[m].x<<' '<<b[m].y<<'\n');
    return 0;
}