Cod sursa(job #1136095)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 8 martie 2014 19:06:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

#define Nmax 120005
#define x first
#define y second
#define pdd pair<double,double>

using namespace std;
int N,vf = 2;
pair<double,double> points[Nmax];
pair<double,double> S[Nmax];

/**
    A.x A.y 1
    B.x B.y 1 = A.x*B.y + B.x*C.y + C.x*A.y - A.y*B.x - B.y*C.x - C.y*A.x;
    C.x C.y 1
**/

double cross(pdd A,pdd B,pdd C)
{
    return A.x*B.y + B.x*C.y + C.x*A.y -
           A.y*B.x - B.y*C.x - C.y*A.x;
}

double dist(pdd A, pdd B)
{
    return sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y));
}

class cmp{
public:
    bool operator()(const pdd A,const pdd B) const
    {
        double x = cross(points[1],A,B);
        if(x) return x < 0;
        return dist(points[1],A) < dist(points[1],B);
    }
};

void read()
{
    scanf("%d",&N);
    for(int i = 1; i <= N; ++i)
        scanf("%lf%lf",&points[i].first,&points[i].second);
    int pz = 1;
    for(int i = 2; i <= N; ++i)
        if(points[i] < points[pz])
            pz = i;
    swap(points[pz],points[1]);
    sort(points+2,points+N+1,cmp());
}

void make_hull()
{
    S[1] = points[1];
    S[2] = points[2];
    for(int i = 3; i <= N; ++i)
    {
        while(vf >= 2 && cross(S[vf-1],S[vf],points[i]) > 0)
            --vf;
        S[++vf] = points[i];
    }
}
void print()
{
    printf("%d\n",vf);
    for(int i = vf; i >= 1; --i)
        printf("%.6lf %.6lf\n",S[i].first,S[i].second);
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    read();
    make_hull();
    print();

    return 0;
}