Cod sursa(job #1745449)

Utilizator TibiraducanuTiberiu Raducanu Tibiraducanu Data 21 august 2016 21:47:13
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const int N=120005, Eps=1e-12;
struct Point
{
    double x,y;
} v[N];

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

double cross_product(Point O, Point A, Point B) {
    return (A.x-O.x)*(B.y-O.y)-(B.x-O.x)*(A.y-O.y);
}

int i,n,pos,r=1,st[N];

int main()
{
    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[1]=1, st[2]=2, pos=2;
    for(i=3;i>0;i+=r)
    {
        if(i==n) r=-1;
        while(pos>=2 and cross_product( v[st[pos-1]], v[st[pos]], v[i] ) < Eps )
            pos--;
        pos++;
        st[pos]=i;
    }

    printf("%d\n",pos-1);
    for(i=1;i<pos;i++) printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);


    return 0;
}