Cod sursa(job #799466)

Utilizator costyv87Vlad Costin costyv87 Data 19 octombrie 2012 00:39:58
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <algorithm>
using namespace std;

FILE *f,*g;

struct cp{double x,y; } ax;
cp v[120100];
int st[120100];
int i,n,mni;
double mnx,mny;


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

int smn(cp a , cp b, cp c)
{
    long double s=0;
    s=(long double)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);
        if (i==1)
            {
                mnx=v[i].x;
                mny=v[i].y;
            }
        if (v[i].x<mnx || (v[i].x==mnx && v[i].y<mny))
        {
              mnx=v[i].x;
              mny=v[i].y;
              mni=i;
        }

    }

    cp ax;
    ax=v[mni];
    v[mni]=v[1];
    v[1]=ax;

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

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

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

    fclose(g);
    return 0;
}