Cod sursa(job #1310463)

Utilizator SagunistuStrimbu Alexandru Sagunistu Data 6 ianuarie 2015 21:22:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <cstdio>
#include <algorithm>
#define x first
#define y second
#define nmax 120010

using namespace std;

pair<double,double> a[nmax];
double eps=10e-12;
int st[nmax],vf;
bool viz[nmax];
int n;

void citire()
{
    double x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&x,&y);
        a[i]=make_pair(x,y);
    }
}

double produs(pair<double,double>&o,pair<double,double>&a,pair<double,double>&b)
{
    return (b.x-o.x)*(a.y-o.y)-(a.x-o.x)*(b.y-o.y);
}

void infasuratoare()
{
    sort(a+1,a+n+1);
    st[1]=1;
    st[2]=2;
    viz[1]=viz[2]=1;
    vf=2;
    for(int i=3;i<=n;i++)
    {
        while(vf>1&&produs(a[st[vf-1]],a[st[vf]],a[i])<eps)
            viz[st[vf--]]=0;
        st[++vf]=i;
        viz[i]=1;
    }
    for(int i=n;i>=1;i--)
    {
        if(viz[i]&&i!=1)
            continue;
        while(vf>1&&produs(a[st[vf-1]],a[st[vf]],a[i])<eps)
            viz[st[vf--]]=0;
        if(i==1)
            continue;
        st[++vf]=i;
        viz[i]=1;
    }
}

void afisare()
{
    printf("%d\n",vf);
    for(int i=vf;i>=1;i--)
        printf("%.6lf %.6lf\n",a[st[i]].x,a[st[i]].y);
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    citire();
    infasuratoare();
    afisare();
    return 0;
}