Cod sursa(job #544242)

Utilizator SadmannCornigeanu Calin Sadmann Data 1 martie 2011 11:56:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *in,*out;
typedef struct punct
{
    double x;
    double y;
};
punct v[120002],P[120002],cont,aux;

int comp_sort(const punct a, const punct b)
{
    if(a.x<b.x)
        return 1;
    if(a.x>b.x)
        return 0;
    if(a.y<b.y)
        return 1;
    return 0;
}

inline bool det_semn(punct b,punct a,punct c)
{
    return (b.x*a.y + c.x*b.y + a.x*c.y - c.x*a.y - b.x*c.y - a.x*b.y)>=0;
}

int n,i,st[120002],pas=1,k;
bool uz[120002];


int main()
{
    in=fopen("infasuratoare.in","rt");
    out=fopen("infasuratoare.out","wt");
    fscanf(in,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(in,"%lf %lf",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,comp_sort);
    uz[2] = 1; st[1] = 1; st[2] = 2; k = 2; i = 3;

    while(!uz[1])
    {
        while(uz[i])
        {
            if(i==n)
                pas=-1;
            i+=pas;
        }
        while(k>=2 && !det_semn(v[st[k-1]],v[st[k]],v[i]))
            uz[st[k--]]=false;
        st[++k]=i;
        uz[i]=true;
    }
    fprintf(out,"%d\n",k-1);
    for(i=1;i<=k-1;i++)
        P[i]=v[st[i]];
    P[k]=P[1];
    for(i=2;i<=k;i++)
        fprintf(out,"%.6lf %.6lf\n",P[i].x,P[i].y);


    return 0;
}