Cod sursa(job #549748)

Utilizator drywaterLazar Vlad drywater Data 8 martie 2011 21:59:14
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
FILE *f=fopen("infasuratoare.in","r"),*g=fopen("infasuratoare.out","w");
int n,i,st[130000],pi;
double a;
struct punct{double x; double y;};
punct p[130000];
int semn(punct a,punct b,punct c)
{
    return (int)(a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x);
}
int cmp(punct a,punct b)
{
   return ((a.x-p[1].x)*(b.y-p[1].y)>(a.y-p[1].y)*(b.x-p[1].x));
}
int main(void)
{
    fscanf(f,"%d",&n);
    pi=1;
    for (i=1;i<=n;i++)
    {
        fscanf(f,"%lf%lf",&p[i].x,&p[i].y);
        if (p[i].x<p[pi].x || (p[i].x==p[pi].x && p[i].y<p[pi].y)) pi=i;
    }
    p[0]=p[1];
    p[1]=p[pi];
    p[pi]=p[0];
    sort(p+2,p+n+1,cmp);
    st[1]=1;
    int k=2;
    for (i=2;i<=n;i++)
    {
        while (k>=2 && semn(p[st[k-2]],p[st[k-1]],p[i])<0) k--;
        st[k]=i;
        k++;
    }
    st[k]=1;
    fprintf(g,"%d\n",k-1);
    for (i=2;i<=k;i++)
        fprintf(g,"%lf %lf\n",p[st[i]].x,p[st[i]].y);
    fclose(g);
    return 0;
}