Cod sursa(job #1153415)

Utilizator Walrus21andrei Walrus21 Data 25 martie 2014 14:15:10
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <stdio.h>
#include <algorithm>
#define nm 120005
#define mxy 1000000001

using namespace std;

FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");

struct p{double x;double y;};

int i,n,k,u;
p v0,v[nm],st[nm];

bool cmp(p A,p B)
{
    return (v0.y-A.y)*(v0.x-B.x)<(v0.y-B.y)*(v0.x-A.x);
}

bool ung(p A,p B,p C)
{
    return A.x*B.y+B.x*C.y+C.x*A.y-A.x*C.y-B.x*A.y-C.x*B.y<0;
}

int main()
{
    fscanf(f,"%d",&n); v0.x=mxy;
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
        if(v[i].x<v0.x||(v[i].x==v0.x&&v[i].y<v0.y)) v0=v[i];
    }
    stable_sort(v+1,v+n+1,cmp);
    st[0]=v0; st[1]=v[1]; st[2]=v[2];
    u=2;
    for(i=3;i<=n;i++)
    {
        while(ung(st[u-1],st[u],v[i])) u--;
        st[++u]=v[i];
    }
    fprintf(g,"%d\n",u+1);
    for(i=0;i<=u;i++)
     fprintf(g,"%lf %lf\n",st[i].x,st[i].y);
    return 0;
}