Cod sursa(job #1523832)

Utilizator andreeainfo_dAndreea Dutulescu andreeainfo_d Data 13 noiembrie 2015 13:15:31
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define eps 0.0000000001
int n,i,u,v[120004];
double st[120004];
struct andreea
{
    int x,y;
}a[120004];
double modul(double xx)
{
    if(xx<0)return xx;
    else return -xx;
}
bool cmp(andreea a, andreea b)
{
    if(modul(a.x-b.x)<eps&&a.x<b.x)return 1;
    else if(modul(a.x-b.x)>eps&&a.y<b.y)return 1;
    return 0;
}
double aria(andreea m, andreea n, andreea p)
{
    return (double)m.x*n.y+n.x*p.y+p.x*m.y-n.y*p.x-p.y*m.x-m.y*n.x;
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lf%lf",a[i].x,a[i].y);
    }
    sort(a+1,a+n+1,cmp);
    u=2;
    st[1]=1;
    st[2]=2;
    v[1]=1;
    v[2]=1;
    for(i=3;i<=n;i++)
    {
        if(v[i]==0)
        {
            while(u>=2&&  aria(a[st[u-1]],  a[st[u]],  a[i])  <eps)
            {
                v[st[u]]=0;
                u--;
            }
            u++;
            st[u]=i;
            v[i]=1;
        }
    }
    for(i=n;i>=1;i++)
    {
        if(v[i]==0)
        {
            while(u>=2&&  aria(a[st[u-1]],  a[st[u]],  a[i])  <eps)
            {
                v[st[u]]=0;
                u--;
            }
            u++;
            st[u]=i;
            v[i]=1;
        }
    }
    printf("%d\n",u);
    for(i=1;i<=u;i++)
    {
        printf("%.6lf %.6lf",a[st[i]].x, a[st[i]].y);
    }
    return 0;
}