Cod sursa(job #1113789)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 20 februarie 2014 21:56:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

#define Nmax 120005
#define x first
#define y second

using namespace std;


pair<double,double> M[Nmax],S[Nmax],P;
int vf = 2;
int N;
/**
    A.x A.y 1
    B.x B.y 1
    C.x C.y 1
    = A.x * B.y + B.x * C.y + C.x * A.y - C.x*B.y - C.y * A.x - B.x * A.y;

*/

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

class cmp{
public:
    bool operator()(const pair<double,double> A, const pair<double,double> B)const
    {
       return cross(M[1],A,B)<0;
    }
};

void convex_hull()
{
    S[1] = M[1];
    S[2] = M[2];
    for(int i = 3; i <= N; ++i)
    {
        while(vf >= 2 && cross(S[vf-1],S[vf],M[i]) > 0)
            --vf;
        S[++vf] = M[i];
    }
}

void afish()
{
    printf("%d\n",vf);
    for(int i = vf; i>= 1; --i)
        printf("%.6lf %.6lf\n",S[i].x,S[i].y);
}

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

    scanf("%d",&N);
    for(int i = 1; i <= N; ++i){
        scanf("%lf%lf",&M[i].first,&M[i].second);
    }

    int pz = 1;
    for(int i = 2; i <= N; ++i)
        if(M[i] < M[pz])
            pz = i;
    swap(M[pz],M[1]);
    sort(M+2,M+N+1,cmp());

    convex_hull();
    afish();

    return 0;
}