Cod sursa(job #1228699)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 14 septembrie 2014 23:15:56
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <algorithm>
#define Nmax 120005
#define eps 0.000000000001

using namespace std;

int N,st[Nmax];
bool fr[Nmax];

struct pc
{
    double x,y;
    bool operator < (const pc &A) const
    {
        return y<A.y;
    }
};
pc v[Nmax];

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

int main()
{
    int i,sign=1,top=2;
    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);
    st[1]=1; st[2]=2;
    fr[1]=fr[2]=true;
    for(i=3;i;i+=sign)
    {
        if(fr[i]) continue;
        while(top>=2 && Prod(v[st[top-1]],v[st[top]],v[i])<eps)
            fr[st[top--]]=false;
        st[++top]=i; fr[i]=true;
        if(st[top]==N) sign=-1;
    }
    printf("%d\n", top);
    for(i=1;i<=top;++i)
        printf("%lf %lf\n", v[st[i]].x,v[st[i]].y);
    return 0;
}