Cod sursa(job #1434690)

Utilizator tudor_bonifateTudor Bonifate tudor_bonifate Data 11 mai 2015 09:33:14
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <algorithm>
#define eps 1e-12
using namespace std;
struct punct
{
    double x;
    double y;
};
punct a[120001];
bool cmp(punct a, punct b)
{
    if (a.y<b.y) return true;
    else if (a.y>b.y) return false;
    else
    {
        if (a.x<b.x) return true;
        else return false;
    }
}
int comp(double a, double b)
{
    if (a+eps<b) return 1;
    if (b+eps<a) return -1;
    return 0;
}
int determinant(punct a, punct b, punct c)
{
    int det=a.x * b.y + c.x * a.y + b.x * c.y - c.x * b.y - b.x * a.y - a.x * c.y;
    return comp(det,0);
}
int st[120001],n,i,nr,nr1,q;
bool ok[120001];
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].x,&a[i].y);
    sort(a+1,a+n+1,cmp);
    st[1]=1;
    st[2]=2;
    nr=2;
    ok[2]=true;
    q=1;
    i=3;
    while (!ok[1])
    {
        while (ok[i])
        {
            if (i==n) q=-1;
            i+=q;
        }
        while (nr>=2 && determinant(a[st[nr]],a[st[nr-1]],a[i])==-1) ok[st[nr--]]=false;
        st[++nr]=i;
        ok[i]=true;
    }
    nr1=nr-1;
    printf("%d\n",nr1);
    for (i=1; i<=nr1; i++) printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
    return 0;
}