Cod sursa(job #798868)

Utilizator costyv87Vlad Costin costyv87 Data 17 octombrie 2012 14:47:06
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <cstdio>
#include <algorithm>
using namespace std;

FILE *f,*g;

struct cp{double x,y;} ax;
cp v[100100];
int st[100100];
int i,n;


bool cmp(cp a, cp b)
{
    return (a.y*b.x<=a.x*b.y);
}

int smn(cp a , cp b, cp c)
{
    double s;
    s=a.x*b.y+ b.x*c.y+ c.x*a.y - a.y*b.x- b.y*c.x- c.y*a.x;
    if (s<0)
        return 0;
    return 1;
}

int main()
{
    f=fopen("infasuratoare.in","r");
    g=fopen("infasuratoare.out","w");

    fscanf(f,"%d",&n);
    for (i=1;i<=n;i++)
    {
        fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
    }
    sort(v+1,v+n+1,cmp);

    st[0]=2;
    st[1]=1;
    st[2]=2;
    for (i=3;i<=n;i++)
    {
        while (st[0]>=1 &&!smn(v[st[st[0]-1]],v[st[st[0]]],v[i]))
                st[0]--;
        st[++st[0]]=i;
    }

    fprintf(g,"%d\n",st[0]);
    for (i=1;i<=st[0];i++)
        fprintf(g,"%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);

    fclose(g);
    return 0;
}