Cod sursa(job #709608)

Utilizator rootsroots1 roots Data 8 martie 2012 12:12:21
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
/*********************************
*Potrivirea lui Jarvis - O( N*H )*
*********************************/

#include <stdio.h>
#include <string.h>

#define maxN 120001

struct punct
{
    double x,y;
}P[maxN],pi,H[maxN];

int use[maxN];

inline int unghi(punct a,punct b,punct c)
{
    return (b.x-a.x)*(c.y-a.y)<(c.x-a.x)*(b.y-a.y);
}

int main()
{
    int N;

    freopen("infasuratoare.in","r",stdin);
    scanf("%d",&N);
    for(int i=1;i<=N;++i) scanf("%lf%lf",&P[i].x,&P[i].y);

    pi=P[1];
    int pos=1;

    for(int i=2;i<=N;++i)
        if(P[i].x<pi.x)
        {
            pi=P[i];
            pos=i;
        }
        else
        if(P[i].x==pi.x&&P[i].y<pi.y)
        {
            pi=P[i];
            pos=i;
        }

    memset(use,0,sizeof(use));
    use[pos]=1;
    int aux=pos;

    int cnt=0;
    H[++cnt]=pi;
    while(1)
    {
        int to=0;

        for(int i=1;i<=N;++i)
            if(!use[i])
            {
                if(to==0) to=i;
                else
                if(unghi(P[pos],P[to],P[i])) to=i;
            }

        if(to==0) break;
        if(unghi(P[pos],P[to],P[aux])) to=aux;
        if(to==aux) break;

        pos=to;
        use[pos]=1;
        H[++cnt]=P[pos];
    }

    freopen("infasuratoare.out","w",stdout);
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;++i)
        printf("%.7lf %.7lf\n",H[i].x,H[i].y);

    return 0;
}