Cod sursa(job #2756365)

Utilizator maria_neagoieMaria Neagoie maria_neagoie Data 31 mai 2021 11:28:02
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int NMAX=120005;
const double eps=1.0e-12;
struct POINT
{
    double x,y;
};
POINT P[NMAX+5],LL;
int h[NMAX+5];
double cp(const POINT &a,const POINT &b,const POINT &c)
{
    return ((b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x));
}
int ccw(const POINT &a,const POINT &b,const POINT &c)
{
    double val_cp;
    val_cp=cp(a,b,c);
    if(fabs(val_cp)<eps) //cp==0
        return 0;
    if(val_cp>=eps)
        return 1; //trigonometric
    return -1; //orar
}
bool cmp(POINT &a,POINT &b)
{
    return ccw(LL,a,b)==1;
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n,i,top;
    double x,y;
    scanf("%d",&n);
    scanf("%lf%lf",&x,&y);
    P[0].x=x;
    P[0].y=y;
    //LL - P[0]
    for(i=1;i<n;i++)
    {
        scanf("%lf%lf",&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])==1)
        {
            h[++top]=i;
            i++;
        }
        else
            top--;
    }
    printf("%d\n",top);
    for(i=0;i<top;i++)
        printf("%lf %lf\n",P[h[i]].x,P[h[i]].y);
    return 0;
}