Cod sursa(job #2756385)

Utilizator star1star21Stefan Birca star1star21 Data 31 mai 2021 11:53:54
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX=120001;
const double eps=1.0e-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)
{
    double val_cp;
    val_cp = cp(a, b, c);
    if (fabs(val_cp) < eps)
        return 0;
    if (val_cp >= 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[0],P[i]);
            }
        }
    }
    LL=P[0];
    sort(P+1,P+n,cmp);
    P[n]=P[0];
    h[0]=0;
    h[1]=1;
    top=1;
    i=2;
    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;
}