Cod sursa(job #1523835)

Utilizator zikade9Irimia Rares zikade9 Data 13 noiembrie 2015 13:20:20
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int nr,n,i,st[120009],ap[120009];
double mod(double x)
{
    if(x<0) return -x;
    return x;
}
double EPS=0.000000000001;
struct ee
{
    double x,y;
}a[120009];
int cmp(ee a, ee b)
{
    if(mod(a.x-b.x)<=EPS) return a.y<b.y;
    return a.x<b.x;
}
double arie(ee a, ee b, ee c)
{
    double x;
    x=(double)a.x*b.y + b.x*c.y + c.x*a.y - b.y*c.x - c.y*a.x - a.y*b.x;
    return x;
}
void elim(int i)
{
    while(nr>=2&&arie(a[st[nr-1]],a[st[nr]],a[i])<EPS)
    {
        ap[st[nr]]=0;
        nr--;
    }
}
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);
    st[1]=1;
    st[2]=2;
    nr=2;
    ap[2]=1;
    for(i=3;i<=n;i++)
    {
        if(ap[i]==0)
        {
            elim(i);
            nr++;
            st[nr]=i;
            ap[i]=1;
        }
    }
    for(i=n;i>=1;i--)
    {
        if(ap[i]==0)
        {
            elim(i);
            nr++;
            st[nr]=i;
            ap[i]=1;
        }
    }
    //elim(1);
    printf("%d\n",nr-1);
    for(i=2;i<=nr;i++)
        printf("%.6lf %.6lf\n",a[st[i]].x,a[st[i]].y);
    return 0;
}