Cod sursa(job #1219155)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 13 august 2014 16:23:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <cstdio>
#include <algorithm>
#include <vector>

#define x first
#define y second
#define EPS 0.00001

using namespace std;
int N;
vector<pair<double,double> >P,hull;
pair<double,double> stak[120005];
int vf;

void push(pair<double,double> P){
    stak[++vf] = P;
}
void pop(){
    stak[vf] = make_pair(0,0);
    --vf;
}
double abso(double nr){
    if(nr < 0)
        return -nr;
    return nr;
}

double semn(pair<double,double> p1, pair<double,double> p2, pair<double,double> p3){
    double rez = (p1.x-p3.x)*(p2.y-p3.y) - (p2.x-p3.x)*(p1.y-p3.y);
    if(abso(rez - 0.0000001) < EPS)
        return 0;
    return rez;
}

void read( void )
{
    pair<double,double> pct;
    scanf("%d",&N);
    for(int i = 1; i <= N; ++i){
        scanf("%lf%lf",&pct.x,&pct.y);
        P.push_back(pct);
    }
}

void solve( void )
{
    sort(P.begin(),P.end());
    pair<double,double> Pmin = P[0],Pmax = P[P.size()-1];
    push(Pmin); /// sigur apartine
    for(int i = 1; i < N; ++i)
        if(semn(Pmin,Pmax,P[i]) >= 0 || i == N)
        {
            while(vf >= 2 && semn(stak[vf-1],stak[vf],P[i]) >= 0) /// fara egal si le ia si pe alea coliniare
                pop();
            push(P[i]);
        }
    for(int i = N - 2; i >= 0; --i)
        if(semn(Pmax,Pmin,P[i]) >=0 || i == 0)
        {
            while(vf >= 2 && semn(stak[vf-1],stak[vf],P[i]) >= 0) /// fara egal si le ia si pe alea coliniare
                pop();
            push(P[i]);
        }
}

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

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

    read();
    solve();
    print();

    return 0;
}