Cod sursa(job #2878547)

Utilizator IoanMihaiIoan Mihai IoanMihai Data 27 martie 2022 10:33:06
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb

#include <bits/stdc++.h>
using namespace std;
ifstream  fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct ceva
{
    long double x,y;
}v[120010];
vector<ceva>upper;
vector<ceva>lower;
int n,i,k;
bool cmp(ceva a,ceva b)
{
    return a.x<b.x || (a.x==b.x && a.y<b.y);
}
long double cp(ceva a,ceva b,ceva c)
{
    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++)
    {
        k=upper.size();
        while(k>=2 && cp(upper[k-1],v[i],upper[k-2])>0)
            upper.pop_back(),k--;
        upper.push_back(v[i]);
        k=lower.size();
        while(k>=2 && cp(lower[k-1],v[i],lower[k-2])<0)
            lower.pop_back(),k--;
        lower.push_back(v[i]);
    }
    fout<<upper.size()+lower.size()-2<<'\n';
    fout<<fixed<<setprecision(12);
    for(i=1;i<lower.size();i++)
        fout<<lower[i].x<<" "<<lower[i].y<<'\n';
    for(i=upper.size()-2;i>=0;i--)
        fout<<upper[i].x<<" "<<upper[i].y<<'\n';
    return 0;
}