Cod sursa(job #3268079)

Utilizator andrei1232008nicolae andrei andrei1232008 Data 13 ianuarie 2025 16:55:19
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,i,k=0;
struct number
{
    double x,y;
} v[120005],s[120005];
void read()
{
    fin>>n;
    for(i=1; i<=n; i++)
        fin>>v[i].x>>v[i].y;
}
double comp(number a,number b)
{
    return ((a.y<b.y)||(a.y==b.y&&a.x<b.x));
}
double comp2(number a,number b)
{
    return ((double)(a.y-v[1].y)*(b.x-v[1].x)<(double)(b.y-v[1].y)*(a.x-v[1].x));
}
double determinant(double xa,double ya,double xb,double yb,double xc,double yc)
{
    return (xb*yc+xc*ya+xa*yb-xb*ya-xc*yb-xa*yc);
}
void solve()
{
    sort(v+1,v+n+1,comp);
    s[++k].x=v[1].x;
    s[k].y=v[1].y;
    sort(v+2,v+n+1,comp2);
    s[++k].x=v[2].x;
    s[k].y=v[2].y;
    for(i=3; i<=n; i++)
    {
        s[++k].x=v[i].x;s[k].y=v[i].y;
        double d=determinant(s[k-2].x,s[k-2].y,s[k-1].x,s[k-1].y,s[k].x,s[k].y);
        while(k>2&&d<0)
        {
            k--;
            s[k].x=v[i].x;s[k].y=v[i].y;
            d=determinant(s[k-2].x,s[k-2].y,s[k-1].x,s[k-1].y,v[i].x,v[i].y);
        }
    }
}
void afis()
{
    fout<<k<<'\n';
    for(i=1; i<=k; i++)
        fout<<fixed<<setprecision(12)<<s[i].x<<" "<<setprecision(12)<<s[i].y<<'\n';
}
int main()
{
    read();
    solve();
    afis();
    return 0;
}