Cod sursa(job #891339)

Utilizator cremarencodianaCremarenco Diana cremarencodiana Data 25 februarie 2013 16:04:54
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <stdio.h>
# include <algorithm>
# include <math.h>
# include <vector>
#define eps 1e-12
using namespace std;
int n,i,in,c,poz,s[120000],h,ok[120000];
bool use[120000];

struct punct
{
    double x; double y;
} p[120000],v[120000];


bool cmp(const punct&a , const punct &b)
{
    if (a.x==b.x)
        return (a.y<b.y);
    return (a.x<b.x);
}


inline int cmp1(double a,double b)
{
        if (a+eps<b) return 1;
        if (b+eps<a) return -1;
        return 0;
}


int semn(punct a, punct b, punct c)
{
    double A,B,C;
    A=a.y-b.y;
    B=b.x-a.x;
    C=a.x*b.y-b.x*a.y;
    return cmp1(A*c.x+B*c.y+C,0);
}


void rezolva()
{
    sort(v+1,v+n+1,cmp);
    int k,q;
    s[1]=1;
    s[2]=2;
    ok[2]=1;
    k=2;
    i=3;
    q=1;
    while (!ok[1])
    {
        while (ok[i])
        {
            if (i==n) q=-1;
            i+=q;
        }
        while (k>=2 && semn (v[s[k-1]],v[s[k]],v[i])==-1)
        {
            ok[s[k--]]=0;
        }
        s[++k]=i;
        ok[i]=1;
    }
    h=k-1;
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d\n",&n);
    for (i=1; i<=n; i++)
    {
        scanf("%lf %lf",&v[i].x,&v[i].y);
    }
    rezolva();
    printf("%d\n",h);
    for (i=2; i<=h+1; i++)
         printf("%lf %lf\n",v[s[i]].x,v[s[i]].y);
    return 0;
}