Cod sursa(job #709224)

Utilizator rootsroots1 roots Data 7 martie 2012 20:39:37
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
/*******************
*N/A - O(N log2 N)*
*******************/

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

#define maxN 120001
#define Error 1

using namespace std;

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

int use[maxN],st[maxN];

inline bool cmp(punct a,punct b)
{
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}

inline int unghi(punct a,punct b,punct c)
{
    return (b.x-a.x)*(c.y-a.y)+Error<(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);

    sort(P+1,P+N+1,cmp);

    memset(use,0,sizeof(use));
    use[1]=1;
    use[2]=1;
    st[0]=2;
    st[1]=1;
    st[2]=2;

    for(int i=3;i<=N;++i)
        if(!use[i])
        {
            while(unghi(P[st[st[0]-1]],P[st[st[0]]],P[i])) use[st[st[0]--]]=0;
            st[++st[0]]=i;
            use[i]=1;
        }

    for(int i=N-1;i>1;--i)
        if(!use[i])
        {
            while(unghi(P[st[st[0]-1]],P[st[st[0]]],P[i])) use[st[st[0]--]]=0;
            st[++st[0]]=i;
            use[i]=1;
        }

    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;
}