Cod sursa(job #705758)

Utilizator rootsroots1 roots Data 4 martie 2012 21:49:21
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
/******************************
*Scanarea Graham - O(N log2 N)*
******************************/

#include <stdio.h>
#include <algorithm>

#define maxN 120001

using namespace std;

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

int St[maxN];
int N;

inline bool cmp(punct a,punct b)
{
    return (a.x-pi.x)*(b.y-pi.y)>(b.x-pi.x)*(a.y-pi.y);
}

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

int main()
{
    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(pi.x>P[i].x) pi=P[i], pos=i;
        else
        if(pi.x==P[i].x&&pi.y>P[i].y) pi=P[i], pos=i;

    pi=P[1];
    P[1]=P[pos];
    P[pos]=pi;
    pi=P[1];
    sort(P+2,P+N+1,cmp);

    St[0]=2;
    St[1]=1;
    St[2]=2;

    for(int i=3;i<=N;++i)
    {
        while(turn(P[St[St[0]-1]],P[St[St[0]]],P[i])) --St[0];
        St[++St[0]]=i;
    }

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

    return 0;
}