Cod sursa(job #1071863)

Utilizator thewildnathNathan Wildenberg thewildnath Data 3 ianuarie 2014 16:45:10
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define NMAX 120010
#define INF 2000000000

struct punct
{
    double x,y,tan;
};
punct v[NMAX];

int sol[NMAX],nr;

inline bool cmp(const punct &a,const punct &b)
{
    return a.tan<b.tan;
}

inline bool det(const punct &a,const punct &b,const punct &c)
{
    double s=(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);
    if(s>=0)
        return 1;
    return 0;

}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n,i,poz=1;
    double xmin=INF,ymin;

    scanf("%d",&n);
    for(i=1;i<=n;++i)
    {
        scanf("%lf%lf",&v[i].x,&v[i].y);
        if(v[i].x<xmin || (v[i].x==xmin&&v[i].y<ymin))
        {
            xmin=v[i].x;
            ymin=v[i].y;
            poz=i;
        }
    }

    v[0]=v[1];
    v[1]=v[poz];
    v[poz]=v[0];
    sol[++nr]=1;

    for(i=1;i<=n;++i)
    {
        v[i].x-=xmin;
        v[i].y-=ymin;

        v[i].tan=v[i].y/v[i].x;
    }

    sort(v+2,v+1+n,cmp);

    /////////
    for(i=2;i<=n;++i)
    {
        sol[++nr]=i;
        while(nr>2 && det(v[sol[nr-1]],v[sol[nr]],v[sol[nr-2]]))
        {
            sol[nr-1]=sol[nr];
            sol[nr]=0;
            --nr;
        }
    }

    printf("%d\n",nr);
    for(i=1;i<=nr;++i)
        printf("%lf %lf\n",v[sol[i]].x+xmin,v[sol[i]].y+ymin);

    return 0;
}