Cod sursa(job #923725)

Utilizator alecsandrualex cuturela alecsandru Data 23 martie 2013 20:03:25
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#define eps 1.e-12
using namespace std;
struct POINT
{
    double x,y;
};
POINT ll,t;
int n,i,top,st[120100],poz;
double a1,a2;
vector <POINT> v;
double ccw(POINT p1,POINT p2,POINT p3)
{
    return (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
}
bool cmp(const POINT &a,const POINT &b)
{
    if(fabs(a.x-ll.x)<eps&&fabs(a.y-ll.y)<eps)
        return 1;
    if(fabs(b.x-ll.x)<eps&&fabs(b.y-ll.y)<eps)
        return 0;
    if(ccw(ll,a,b)>eps)
        return 1;
    return 0;
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    ll.x=1000000001;
    ll.y=1000000001;
    for(i=1;i<=n;i++)
    {
        scanf("%lf%lf",&a1,&a2);
        t.x=a1;
        t.y=a2;
         if(t.y-ll.y<-eps)
        {
                ll.x=t.x;
                ll.y=t.y;
        }
        if(fabs(t.y-ll.y)<eps)
        {
            if(t.x-ll.x<-eps)
            {
                ll.x=t.x;
                ll.y=t.y;
            }
        }
        v.push_back(t);
    }
    sort(v.begin(),v.end(),cmp);
    v.push_back(ll);
    st[0]=0;
    st[1]=1;
    top=1;
    i=2;
    while(i<=n)
    {
        if(ccw(v[st[top-1]],v[st[top]],v[i])>eps)
        {
            st[++top]=i;
            i++;
        }
        else
            top--;
    }
    printf("%d\n",top);
    for(i=0;i<top;i++)
        printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
    return 0;
}