Cod sursa(job #1375528)

Utilizator andru47Stefanescu Andru andru47 Data 5 martie 2015 13:30:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#define f first
#define s second
#define eps 1e-12
#define pairr pair < double , double >
using namespace std;
int b[125000],n,k,i,instr;
bool ok[125000];
pairr a[125000];
int cmpp(double x,double y)
{
    if (x+eps<y)return -1;
    else if (y+eps<x)return 1;
    return 0;
}
int cmp(pairr a,pairr b,pairr c)
{
    double A,B,C;
    A=a.s-b.s;
    B=b.f-a.f;
    C=a.f*b.s-b.f*a.s;
    return (cmpp(A*c.f+B*c.s+C,0));
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d\n",&n);
    for (i=1; i<=n; i++)
    {
        scanf("%lf %lf\n",&a[i].f,&a[i].s);
    }
    sort(a+1,a+n+1);
    ok[2]=true;
    i=3;
    instr=0;
    b[++k]=1;
    b[++k]=2;
    while(ok[1]==false)
    {
        while (ok[i]==true)
        {
            if (i==n)instr=1;
            if (instr==1)i--;
            else i++;
        }
        while(k>=2&&cmp(a[b[k-1]],a[b[k]],a[i])==-1)
        {
            ok[b[k--]]=false;
        }
        b[++k]=i;
        ok[i]=true;
    }
    printf("%d\n",k-1);
    for (i=2; i<=k; i++)
        printf("%lf %lf\n",a[b[i]].f,a[b[i]].s);
    return 0;
}