Cod sursa(job #2194113)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 12 aprilie 2018 13:11:05
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1.e-14;
struct dd
{
    double x,y;
}ll;
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)
{
    int r=cp(a,b,c);
    if(r<0)return -1;
    return 1;
}
bool cmp(dd a,dd b)
{
    int s=ccw(ll,a,b);
    if(s>0)return 1;
    return 0;
}
dd a[120005];
dd v[120005];
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n , i;
    scanf("%d",&n);
    scanf("%lf%lf",&ll.x,&ll.y);
    a[0]=ll;
    for(i=1;i<n;i++)
        {
            scanf("%f%f",&a[i].x,&a[i].y);
            if(fabs(ll.y-a[i].y)<eps)
            {
                if(ll.x-a[i].x>eps)
                    {
                        ll=a[i];
                        a[i]=a[0];
                        a[0]=ll;
                    }
            }
            if(ll.y-a[i].y>eps)
                {
                                            ll=a[i];
                        a[i]=a[0];
                        a[0]=ll;
                }
        }
        sort(a+1,a+n,cmp);
        int cnt=2;
        v[1]=ll;
        v[2]=a[1];
        for(i=2;i<n;i++)
        {
            dd t1=v[cnt-1],t2=v[cnt];
            while(ccw(t1,t2,a[i])<0)
            {
                --cnt;
                t1=v[cnt-1],t2=v[cnt];
            }
            cnt++;
            v[cnt]=a[i];
        }
        printf("%d\n",cnt);
        for(i=1;i<=cnt;i++)
            printf("%lf %lf\n",v[i].x,v[i].y);
    return 0;
}