Cod sursa(job #1509801)

Utilizator gbibBacotiu Gabi gbib Data 24 octombrie 2015 12:25:31
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#define eps 1e-12
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct point{double x,y;} a[120004];

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)
{
    a.x-=o.x;
    a.y-=o.y;
    b.x-=o.x;
    b.y-=o.y;
    return (a.x*b.y-a.y*b.x);
}
int st[120002],viz[120002];
int main()
{int n,i,vf=0;
    in>>n;
    for(i=1;i<=n;i++)
    {
        in>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,cmp);
    st[1]=1;
    st[2]=2;
    vf=2;
    for(i=3;i<=n;i++)
    {
        while(vf>=2&&cross_product(a[st[vf-1]],a[st[vf]],a[i])<eps)
        {
            vf--;
        }
        st[++vf]=i;
    }
    int st2[120002],vf2;
    st2[1]=1;
    st2[2]=2;
    vf2=2;
    for(i=n-2;i>=2;i--)
    {
        while(vf2>=2&&cross_product(a[st2[vf2-1]],a[st2[vf2]],a[i])<eps)
        {
            vf2--;
        }
        st2[++vf2]=i;
    }
    out<<vf+vf2-2<<'\n';
    for(i=1;i<vf;i++)
        out<<setprecision(6)<<fixed<<a[st[i]].x<<" "<<a[st[i]].y<<'\n';
    for(i=1;i<vf2;i++)
        out<<setprecision(6)<<fixed<<a[st[i]].x<<" "<<a[st[i]].y<<'\n';
    return 0;
}