Cod sursa(job #474225)

Utilizator ionutz32Ilie Ionut ionutz32 Data 2 august 2010 22:39:19
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int n,i,point,stack[120005],nrs;
double x,y;
pair<double,double> v[120005];
struct cmp
{
    inline bool operator()(const pair<double,double> &a,const pair<double,double> &b)const
    {
        if (a.first==x && a.second==y)
            return 1;
        if (b.first==x && b.second==y)
            return 0;
        if (a.first==x)
            return 0;
        if (b.first==x)
            return 1;
        return ((long double)(a.second-y)/(a.first-x)<(long double)(b.second-y)/(b.first-x));
    }
};

inline bool dif(int dr1,int dr2,int punct)
{
    if (v[dr1].first==v[dr2].first)
        return (x<v[dr1].first && v[punct].first>v[dr1].first);
    long double a,b,val1,valpct;
    a=(long double)(v[dr1].second-v[dr2].second)/(v[dr1].first-v[dr2].first);
    b=v[dr1].second-a*v[dr1].first;
    val1=a*v[1].first+b-v[1].second;
    valpct=a*v[punct].first+b-v[punct].second;
    return (val1>0 && valpct<0) || (val1<0 && valpct>0);
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d %lf %lf",&n,&x,&y);
    v[1]=make_pair(x,y);
    point=1;
    for (i=2;i<=n;++i)
    {
        scanf("%lf %lf",&x,&y);
        v[i]=make_pair(x,y);
        if (v[i].first<v[point].first || (v[i].first==v[point].first && v[i].second<v[point].second))
            point=i;
    }
    x=v[point].first;
    y=v[point].second;
    sort(v+1,v+n+1,cmp());
    nrs=1;
    stack[1]=1;
    for (i=2;i<=n;++i)
    {
        while (nrs>=3 && dif(stack[nrs],stack[nrs-1],i))
            --nrs;
        stack[++nrs]=i;
    }
    printf("%d\n",nrs);
    for (i=1;i<=nrs;++i)
        printf("%lf %lf\n",v[stack[i]].first,v[stack[i]].second);
    return 0;
}