Cod sursa(job #903336)

Utilizator the@EyE@Postavaru Stefan the@EyE@ Data 1 martie 2013 20:06:56
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#define ER 1e-12

using namespace std;

struct point
{
    double x,y;
};

int cmp(double a,double b)
{
    if(a+ER<b)return -1;
    if(b+ER<a)return 1;
    return 0;
}

int Pcmp(point p1,point p2)
{
    int r=cmp(p1.x,p2.x);
    if(r==0)return cmp(p1.y,p2.y)==-1;
    return r==-1;
}

int sgn(point p1,point p2,point p3)
{
    return cmp(p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p2.y*p3.x-p3.y*p1.x-p1.y*p2.x,0);
}

vector<point> points;
vector<int> Q;
int n,used[120002];

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        point p;
        scanf("%lf%lf",&p.x,&p.y);
        points.push_back(p);
    }
    sort(points.begin(),points.end(),Pcmp);
    Q.push_back(0);Q.push_back(1);
    used[1]=1;
    int step=1,ind=2;
    while(ind!=0)
    {
        while(used[ind])
        {
            if(ind==n-1)step=-1;
            ind+=step;
        }
        while(Q.size()>1&&sgn(points[Q[Q.size()-1]],points[Q[Q.size()-2]],points[ind])==-1){used[Q.back()]=0;Q.pop_back();}
        Q.push_back(ind);
        used[ind]=1;
    }
    Q.pop_back();
    printf("%d\n",Q.size());
    for(int i=Q.size()-1;i>=0;--i)printf("%lf %lf\n",points[Q[i]].x,points[Q[i]].y);

    return 0;
}