Cod sursa(job #1375895)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 5 martie 2015 14:56:01
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <cstdio>
#include <algorithm>

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

using namespace std;
int N,vf,used[Nmax];

pair<double,double> P[Nmax],Stack[Nmax];

void push(pair<double,double> P){
    Stack[++vf] = P;
}
void pop(){
    Stack[vf--] = make_pair(0,0);
}

double abso(double d){
    if(d > 0)
        return d;
    return -d;
}

int det(pair<double,double> A, pair<double,double> B, pair<double,double> C)
{
    double d = (A.x - C.x)*(B.y - C.y) -
               (A.y - C.y)*(B.x - C.x);
    if(abso(d) < EPS)
        return 0;
    if(d > 0) return 1;
    return -1;
}

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

void Hull()
{
    pair<double,double> Pmin,Pmax;
    sort(P+1,P+N+1);
    Pmin = P[1]; Pmax = P[N];
    push(Pmin);
    for(int i = 2; i <= N; ++i)
        if(det(Pmin,Pmax,P[i]) >= 0)
        {
            used[i] = 1;
            while(vf >= 2 && det(Stack[vf-1],Stack[vf],P[i]) > 0) /// cu >= scoate punctele coliniare
                pop();
            push(P[i]);
        }
    for(int i = N - 1; i >= 1; --i)
        if(!used[i])
        {
            used[i] = 1;
            while(vf >= 2 && det(Stack[vf-1],Stack[vf],P[i]) > 0)
                pop();
            push(P[i]);
        }
}

void Print()
{
    printf("%d\n",vf - 1);
    pop();
    while(vf >= 1){
        printf("%lf %lf\n",Stack[vf].x, Stack[vf].y);
        pop();
    }
}

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

    Read();
    Hull();
    Print();

    return 0;
}