Cod sursa(job #1640012)

Utilizator danyro364Savu Ioan Daniel danyro364 Data 8 martie 2016 15:18:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#define nmax 120001
using namespace std;
FILE *f=fopen("infasuratoare.in","r"),*g=fopen("infasuratoare.out","w");
struct punct{
    double x,y;
}v[nmax];
int cmp(punct a, punct b)
{
    if(a.x<b.x)
        return 1;
    if(a.x==b.x&&a.y<b.y)
        return 1;
    return 0;
}
int det(punct a, punct b, punct c)
{
    return (a.x*b.y+b.x*c.y+a.y*c.x-b.y*c.x-a.x*c.y-a.y*b.x)<0;
}
int n,st[nmax],k,viz[nmax];
int main()
{
    int i,j,mod=1;
    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[++k]=1;
    st[++k]=2;
    viz[2]=1;
    for(i=3;i>0;i+=mod)
        if(!viz[i])
    {
        while(k>1&&det(v[st[k-1]],v[st[k]],v[i]))
            viz[st[k--]]=0;
        st[++k]=i;
        viz[i]=1;
        if(i==n)
            mod=-1;
    }
    fprintf(g,"%d\n",k-1);
    for(i=1;i<k;i++)
        fprintf(g,"%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
    fclose(f); fclose(g);
    return 0;
}