Cod sursa(job #2571373)

Utilizator maria_neagoieMaria Neagoie maria_neagoie Data 4 martie 2020 22:40:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.16 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps=1.0e-12;
const int NMAX=120005,INF=2000000000;
struct POINT
{
    double x,y,unghi;
};
POINT P[NMAX],st[NMAX];
double rad_to_grad(double x)
{
    double u;
    u=(180*x)/M_PI;
    return u;
}
double unghi_3_puncte(POINT A,POINT O,POINT B)
{
    double dif,unghi;
    dif=fabs(atan2(A.y-O.y,A.x-O.x)-atan2(B.y-O.y,B.x-O.x));
    if(dif-M_PI>=eps)
        dif=2*M_PI-dif;
    unghi=rad_to_grad(dif);
    return unghi;
}
bool cmp(POINT P1,POINT P2)
{
    if(P1.unghi==P2.unghi && P1.x==P2.x)
        return (P1.y>P2.y);
    if(P1.unghi==P2.unghi)
        return (P1.x>P2.x);
    return (P1.unghi<P2.unghi);
}
double cp(POINT P1,POINT P2,POINT P3)
{
    return ((P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x));
}
int ccw(POINT P1,POINT P2,POINT P3)
{
    double val_cp;
    val_cp=cp(P1,P2,P3);
    if(fabs(val_cp)<eps)
        return 0;
    if(val_cp>=eps)
        return 1;
    return -1;
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n,i,ind0,top;
    double tempx,tempy;
    POINT P0,A,O,B;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lf%lf",&tempx,&tempy);
        P[i].x=tempx;
        P[i].y=tempy;
    }
    P0.x=INF;
    P0.y=INF;
    for(i=1;i<=n;i++)
    {
        if(P[i].y-P0.y<=-eps || (fabs(P[i].y-P0.y)<eps && P[i].x-P0.x<=-eps))
        {
            P0=P[i];
            ind0=i;
        }
    }
    for(i=ind0+1;i<=n;i++)
        P[i-1]=P[i];
    O=P0;
    B.x=O.x+1;
    B.y=O.y;
    for(i=1;i<n;i++)
    {
        A=P[i];
        P[i].unghi=unghi_3_puncte(A,O,B);
    }
    sort(P+1,P+n,cmp);
    top=0;
    st[++top]=P0;
    st[++top]=P[1];
    st[++top]=P[2];
    for(i=3;i<n;i++)
    {
        if(fabs(P[i].unghi-P[i-1].unghi)>=eps)
        {
            while(ccw(st[top-1],st[top],P[i])==-1)
                top--;
            st[++top]=P[i];
        }
    }
    printf("%d\n",top);
    for(i=1;i<=top;i++)
        printf("%lf %lf\n",st[i].x,st[i].y);
    fclose(stdin);
    fclose(stdout);
    return 0;
}