Cod sursa(job #1435440)

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