Cod sursa(job #1973043)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 24 aprilie 2017 12:07:15
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <algorithm>
#define x first
#define y second
using namespace std;
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
typedef pair<double,double> punct;
punct st[120005];
punct V[120005];
int dim,N;
double det(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;
}
int main()
{
    fscanf(f,"%d",&N);
    for(int i=1;i<=N;i++)
    {
        fscanf(f,"%lf %lf",&V[i].x,&V[i].y);
    }
    sort(V+1,V+1+N);
    st[++dim]=V[1];
    st[++dim]=V[2];
    for(int i=3;i<=N;i++)
    {
        while(dim>1&&det(st[dim-1],st[dim],V[i])<0)
            dim--;
        st[++dim]=V[i];
    }
    for(int i=N-1;i;i--)
    {
        while(dim>1&&det(st[dim-1],st[dim],V[i])<0)
            dim--;
        st[++dim]=V[i];
    }
    dim--;
    fprintf(g,"%d\n",dim);
    for(int i=1;i<=dim;i++)
        fprintf(g,"%f %f\n",st[i].x,st[i].y);
    fclose(f);
    fclose(g);
    return 0;
}