Cod sursa(job #2754006)

Utilizator un_fes_galbendaniel guba un_fes_galben Data 24 mai 2021 20:44:43
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
const double eps=1.0e-14;
struct punct
{
    double x,y;
}v[120005];
punct LL;
double cp(punct p1,punct p2,punct p3)
{
    return (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
}
int ccw(punct p1,punct p2,punct p3)
{
    if(fabs(cp(p1,p2,p3))<eps){return 0;}
    if(cp(p1,p2,p3)>=eps){return 1;}
    return -1;
}
bool cmp(punct p1,punct p2)
{
    return ccw(LL,p1,p2)>0;
}
int h[120005];
int main()
{
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    int n,poz,i;
    fin>>n;
    fin>>v[0].x>>v[0].y;
    for(i=1;i<n;i++)
    {
        fin>>v[i].x>>v[i].y;
        if(v[i].y-v[0].y<=-eps||(fabs(v[i].y-v[0].y<eps)&&v[i].x-v[0].x<=-eps))
        {
            swap(v[0],v[i]);
        }
    }
    LL=v[0];
    sort(v+1,v+n,cmp);
    h[0]=0;h[1]=1;poz=1;i=2;
    v[n]=v[0];
    while(i<=n)
    {
        if(ccw(v[h[poz-1]],v[h[poz]],v[i])>0)
        {
            h[++poz]=i;
            i++;
        }
        else
        {
            poz--;
        }
    }
    fout<<poz<<'\n';
    for(int i=0;i<poz;i++)
    {
        fout<<fixed<<showpoint<<setprecision(6)<<v[h[i]].x<<" ";
        fout<<fixed<<showpoint<<setprecision(6)<<v[h[i]].y<<'\n';
    }
    return 0;
}