Cod sursa(job #2428165)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 4 iunie 2019 09:38:23
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
using namespace std;
struct dd
{
    double  x,y;
};
const double eps=1.e-14;
int distanta(dd a,dd b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
double cp(dd a,dd b, dd c)
{
    return -(c.x-b.x)*(b.y-a.y)+(c.y-b.y)*(b.x-a.x);
}
int ccw(dd a,dd b,dd c)
{
    double e=cp(a,b,c);
    if(e>=-1*eps)return 1;
    return -1;
}
dd ll;
bool cmp(dd a,dd b)
{
    if(ccw(ll,a,b)>0)return 1;
    return 0;
}
dd v[150005];
dd st[150005];
int main()
{
    freopen("infasuratoareconvexa.in","r",stdin);
    freopen("infasuratoareconvexa.out","w",stdout);
    int n ,i , j;
    scanf("%d",&n);
    scanf("%lf%lf",&ll.x,&ll.y);
    v[0]=ll;
    for(i=1;i<n;i++)
    {
        scanf("%lf%lf",&v[i].x,&v[i].y);
        if(fabs(ll.y-v[i].y)<=eps)
        {
            if(ll.x-v[i].x>=eps)
            {
                ll=v[i];
                v[i]=v[0];
                v[0]=ll;
            }
        }
        if(ll.y-v[i].y>=eps)
        {
            ll=v[i];
            v[i]=v[0];
            v[0]=ll;
        }
    }
    sort(v+1,v+n,cmp);
    int cnt1=2;
    st[1]=v[0];
    st[2]=v[1];
    for(i=2;i<n;i++)
    {
        while(cnt1>=2&&ccw(st[cnt1-1],st[cnt1],v[i])<0)--cnt1;
        st[++cnt1]=v[i];
    }
    printf("%d\n",cnt1);
    for(i=1;i<=cnt1;i++)
        printf("%lf %lf\n",st[i].x,st[i].y);
    return 0;
}