Cod sursa(job #3346089)

Utilizator iustin.dumiDumitrescu Iustin iustin.dumi Data 12 martie 2026 15:30:43
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct pct
{
    double x;
    double y;
}a[120005];
int n,minc,i;
double det(pct a, pct b,pct 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 comp(pct c, pct b)
{
    return (det(a[1],c,b)>0);
}
int main()
{
    fin>>n;
    minc=1;
    for(i=1;i<=n;i++)
    {
        fin>>a[i].x>>a[i].y;
        if(a[i].x<a[minc].x || a[i].x==a[minc].x && a[i].y<a[minc].y)
            minc=i;
    }
    swap(a[1].x,a[minc].x);
    swap(a[1].y,a[minc].y);
    sort(a+2,a+n+1,comp);
    int st=2;
    a[n+1]=a[1];
    for(i=3;i<=n+1;i++)
    {
        while(st>=2 && det(a[st-1],a[st],a[i])<0) st--;
        a[++st]=a[i];
    }
    fout<<st-1<<'\n';
    for(i=1;i<st;i++)
        fout<<fixed<<setprecision(12)<<a[i].x<<" "<<a[i].y<<'\n';
    return 0;
}