Cod sursa(job #1125321)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 26 februarie 2014 16:54:36
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

#define inFILE "infasuratoare.in"
#define outFILE "infasuratoare.out"
#define x first
#define y second

#define Nmax 120005

using namespace std;
pair<double,double> pct[Nmax];
pair<double,double> stak[Nmax],P;
int N,vf=2;

double cross_prod(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 -
           A.y*B.x - B.y*C.x - C.y*A.x;
}
class cmp{
public:
    bool operator()(const pair<double,double>A,const pair<double,double>B)const
    {
        double v1 = atan2(A.y-P.y,A.x-P.x);
        double v2 = atan2(B.y-P.y,B.x-P.x);
        return v1 < v2;
    }
};

void read()
{
    scanf("%d",&N);
    for(int i = 1; i <= N; ++i){
        scanf("%lf%lf",&pct[i].x,&pct[i].y);
        P.x += pct[i].x;
        P.y += pct[i].y;
    }
    P.x /= N;
    P.y /= N;
}

void make_hull()
{
    sort(pct+1,pct+N+1,cmp());
    pct[N+1] = pct[1]; ++ N;
    stak[1] = pct[1];
    stak[2] = pct[2];
    for(int i = 3; i <= N; ++i)
    {
        while(vf >= 2 && cross_prod(stak[vf-1],stak[vf],pct[i]) < 0)
            --vf;
        stak[++vf] = pct[i];
    }
}

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

int main()
{
    freopen (   inFILE, "r", stdin );
    freopen (   outFILE, "w", stdout );

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

    return 0;
}