Cod sursa(job #3268074)

Utilizator amunnumeVlad Patrascu amunnume Data 13 ianuarie 2025 16:51:02
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int N=120005,inf=2e9;
struct elem
{
    double x,y;
}v[N];
int n,i,j,x,y,s[N],sz;
elem sol[N];
double det(double x,double y,double x2,double y2,double x3,double y3)
{
    return x*y2+x2*y3+x3*y-x3*y2-x*y3-x2*y;
}
bool cmp(elem a,elem b)
{
    double dy1=a.y-y;
    double dy2=b.y-y;
    double dx1=a.x-x;
    double dx2=b.x-x;
    double cad1,cad2;

    if(!dy1) cad1=0.5;
    else if(dx1<0) cad1=2;
    else if(!dx1) cad1=1.5;
    else if(dx1>0) cad1=1;

    if(!dy2) cad2=0.5;
    else if(dx2<0) cad2=2;
    else if(!dx2) cad2=1.5;
    else if(dx2>0) cad2=1;

    if(cad1!=cad2)
        return cad1<cad2;
    else
        return dy1*dx2<dx1*dy2;
}
void read()
{
    fin>>n;
    for(i=1;i<=n;++i)
    {
        fin>>v[i].x>>v[i].y;
    }
}
void init()
{
    x=inf;
    y=inf;
    for(i=1;i<=n;++i)
    {
        if(v[i].y<y)
        {
            y=v[i].y;
            j=i;
            x=v[i].x;
        }
        else if(v[i].y==y && v[i].x<x)
        {
            x=v[i].x;
            j=i;
        }
    }
    swap(v[j],v[1]);
    sort(v+2,v+n+1,cmp);
}
void print(double x)
{
    fout<<fixed<<setprecision(6)<<x;
}
double solve()
{
    sz=2;
    s[1]=1;
    s[2]=2;
    for(i=3;i<=n;++i)
    {
        while(sz>=2 && det(v[i].x,v[i].y,v[s[sz]].x,v[s[sz]].y,v[s[sz-1]].x,v[s[sz-1]].y)>0)
        {
            --sz;
        }
        s[++sz]=i;
    }
    fout<<sz<<'\n';
    x=y=0;
    for(i=1;i<=sz;++i)
    {
        sol[i].x=v[s[i]].x;
        sol[i].y=v[s[i]].y;
    }
    x=0; y=0;
    sort(sol+1,sol+sz+1,cmp);
    for(i=1;i<=sz;++i)
    {
        print(sol[i].x); fout<<' ';
        print(sol[i].y); fout<<'\n';
    }
}
int main()
{
    read();
    init();
    solve();
    return 0;
}