Cod sursa(job #798888)

Utilizator lehman97Dimulescu David lehman97 Data 17 octombrie 2012 15:21:56
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <stdio.h>;
#include <algorithm>;
using namespace std;

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

int n;
struct punct {
double x,y;
};
punct v[120001];
int i,st[120001];


int semn(punct a,punct b, punct c)
{
    return(a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x);
}


bool cmp(punct a,punct b)
{
    return(a.x*b.y>=a.y*b.x);

}

int main()
{
    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 && semn(v[st[0]],v[st[0]-1],v[i])>0) st[0]--;
        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;
}