Cod sursa(job #3300601)

Utilizator KapetaneAvram Armand-Florin Kapetane Data 17 iunie 2025 18:43:08
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
using namespace std;

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

struct P
{
    long double x,y;
}v[150005];

int n,s[150005],top,pos;
long double xmin,ymin=1e18L;

int comp(const P &a,const P &b)
{
 return a.x*b.y>=b.x*a.y;
}

bool convex(P a,P b,P c)
{
 long double r=a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
 return r>0;
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
        if(v[i].y<ymin)
        {
        ymin=v[i].y;
        xmin=v[i].x;
        pos=i;
        }
    }
    for(int i=1;i<=n;i++)
    {
    v[i].x-=xmin;
    v[i].y-=ymin;
    }

    swap(v[1],v[pos]);
    sort(v+2,v+n+1,comp);
    s[1]=1;
    s[2]=2;
    top=2;
    for(int i=3;i<=n;i++)
    {
    while(top>=3&&!convex(v[s[top-1]],v[s[top]],v[i]))top--;
    s[++top]=i;
    }
    fout<<top<<endl;
    fout<<fixed<<setprecision(10);
    for(int i=1;i<=top;i++)
    fout<<v[s[i]].x+xmin<<' '<<v[s[i]].y+ymin<<endl;
    return 0;
}