Cod sursa(job #1199015)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 17 iunie 2014 22:45:28
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstdio>
#include <algorithm>
#define Nmax 120005
#define eps 0.000000000001

using namespace std;

struct pc
{
    double x,y;
};
pc v[Nmax];
int st[Nmax],top;
bool viz[Nmax];

inline bool Cmp(const pc A, const pc B)
{
    if(A.y==B.y)
        return A.x<B.x;
    return A.y<B.y;
}

inline double Semn(pc A, pc B, pc C)
{
    return -(C.x-A.x)*(B.y-A.y)+(B.x-A.x)*(C.y-A.y);
}

int main()
{
    int i,sign=1,N;
    freopen ("infasuratoare.in","r",stdin);
    freopen ("infasuratoare.out","w",stdout);
    scanf("%d", &N);
    for(i=1;i<=N;++i)
        scanf("%lf%lf", &v[i].x, &v[i].y);
    sort(v+1,v+N+1,Cmp);
    st[++top]=1; st[++top]=2; viz[2]=true;
    for(i=3;i;i+=sign)
        if(!viz[i])
        {
            while(top>1 && Semn(v[st[top-1]],v[st[top]],v[i])<=eps)
                viz[st[top--]]=false;
            st[++top]=i; viz[i]=true;
            if(i==N)
                sign=-1;
        }
    printf("%d\n", top-1);
    for(i=1;i<top;++i)
        printf("%.6lf %.6lf\n", v[st[i]].x, v[st[i]].y);
    return 0;
}