Cod sursa(job #1349748)

Utilizator ade_tomiEnache Adelina ade_tomi Data 20 februarie 2015 14:20:13
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#define eps 1e-12
#define N 120003
#define x first
#define y second
using namespace std;
typedef pair<double,double> point;

point v[N];

int st[N],i,k,n,f[N];
double cp(point a, point b,point c)
{

    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool cmp (point a, point b)
{

    if(a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}
int main()
{

    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lf%lf",&v[i].x,&v[i].y);
    sort(v+1,v+1+n,cmp);
    st[1]=1;
    st[2]=2;
    k=2;
    for(i=3;i<=n;i++)
    {
        while(k>=2&&cp(v[st[k-1]],v[st[k]],v[i])<=eps)
            k--;
        k++;
        st[k]=i;

    }
    for(i=1;i<=k;i++)
        f[st[i]]=1;
    f[1]=0;
    for(i=n;i>=1;i--)
    {
        if(f[i]==1)
            continue;
        while(k>=2&&cp(v[st[k-1]],v[st[k]],v[i])<=eps)
            k--;
        k++;
        st[k]=i;

    }
    printf("%d\n",k-1);
    for(i=1;i<k;i++)
        printf("%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
    return 0;
}