Cod sursa(job #2495449)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 19 noiembrie 2019 13:52:03
Problema Infasuratoare convexa Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;
struct dd
{
    double x,y;
};
const double eps=1e-14;
double cp(dd a,dd b,dd c)
{
    return(b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
}
int ccw(dd a,dd b,dd c)
{
    double ccp=cp(a,b,c);
    if(ccp>=-eps)return 1;
    return 0;
}
dd ll;
dd v[100005];
bool cmp(dd a ,dd b)
{
    return ccw(ll,a,b);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    dd a,b,c;
    ll.x=1000000001;
    ll.y=1000000001;
    int n,i;
    scanf("%d",&n);
    scanf("%lf%lf",&ll.x,&ll.y);
    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);
    dd st[100005];
    int cnt=2;
    st[1]=ll;st[2]=v[1];
    for(i=2;i<n;i++)
    {
        while(ccw(st[cnt-1],st[cnt],v[i])!=1&&cnt>=2)
            --cnt;
        st[++cnt]=v[i];
    }
    cout<<cnt<<"\n";
    for(i=1;i<=cnt;i++)
        printf("%.6lf %.6lf\n",st[i].x,st[i].y);
    return 0;
}