Cod sursa(job #2756371)

Utilizator CristeaCristianCristea Cristian CristeaCristian Data 31 mai 2021 11:35:52
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX=120000;
const double eps=1e-14;
struct POINT
{
    double x,y;
};
POINT P[NMAX+5],LL;
int h[NMAX+5];
double cp(POINT&a, POINT&b, POINT&c)
{
    return 1.0*(b.x-a.x)*(c.y-b.y)-1.0*(b.y-a.y)*(c.x-b.x);
}
int ccw(POINT&a, POINT&b, POINT&c)
{
    if(fabs(cp(a,b,c))<eps)
        return 0;
    if(cp(a,b,c)>eps)
        return 1;
    return -1;
}
bool cmp(POINT&a,POINT&b)
{
    return ccw(LL,a,b)>0;
}
int main()
{
    int n,i,top;
    double x,y;
    fin>>n>>x>>y;
    P[0].x=x;
    P[0].y=y;
    for(i=1;i<n;i++)
    {
        fin>>x>>y;
        P[i].x=x;
        P[i].y=y;
        if(fabs(y-P[0].y)<eps)
        {
            if(x-P[0].x<=-eps)
                swap(P[0],P[i]);
        }
        else if(y-P[0].y<=-eps)
            swap(P[i],P[0]);
    }
    LL=P[0];
    sort(P+1,P+n,cmp);
    P[n]=P[0];
    h[0]=0;
    h[1]=1;
    top=1;
    i=2;
    /*for(i=0;i<n;i++)
    {
        fout<<P[i].x<<' '<<P[i].y<<'\n';
    }*/
    while(i<=n)
    {
        if(ccw(P[h[top-1]],P[h[top]],P[i])>0)
        {
            h[++top]=i;
            i++;
        }
        else
            top--;
    }
    fout<<top<<'\n';
    for(i=0;i<top;i++)
    {
        fout<<fixed<<setprecision(12)<<P[h[i]].x<<' '<<P[h[i]].y<<'\n';
    }
    return 0;
}