Cod sursa(job #1009779)

Utilizator Viva12Ferentz Sergiu Viva12 Data 13 octombrie 2013 20:32:56
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.53 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#include <queue>
#include <iomanip>
#define oo 1<<15
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair<double,double>points[120100];
pair<double,double> minPoint;
int n;
stack< pair<double,double> >hull;
stack< pair<double,double> > afisHull;
double panta(pair<double,double> A, pair<double,double> B){
    if(A.first == B.first)
    return oo;

    return (B.second - A.second) / (B.first - A.first);

}

bool cmp(pair<double,double> A, pair<double,double> B){
    return panta(minPoint,A) < panta(minPoint,B);
}

void scan(){

    fin >> n;
    int position = 0;
    for(int i =0 ; i < n; i++){

        double x,y;
        fin >> x >> y;
        points[i].first = x;
        points[i].second = y;
        if(i == 0)
        minPoint = points[0];
        else
            if(points[i].first < minPoint.first || (points[i].first == minPoint.first) && (points[i].second < minPoint.second))
            {
                minPoint = points[i];
                position = i;
            }
    }

    points[position] = points[n-1];
    n--;
    points[n].first = 0;
    points[n].second =0;
    sort(points,points+n,cmp);
}

double getDeterminate(pair<double, double> p1, pair<double, double> p2, pair<double, double> p3){

   return (p1.first * p2.second) + (p3.first * p1.second) + (p2.first * p3.second) -
    (p2.second * p3.first) - (p3.second * p1.first) - (p1.second * p2.first);
}

void createHull(){

    hull.push(minPoint);
    hull.push(points[0]);
    for(int i = 1; i < n;i++){

        pair <double, double> p1,p2,p3;
        p3 = points[i];
        p2 = hull.top();
        hull.pop();
        p1 = hull.top();
        hull.pop();
        if(getDeterminate(p1,p2,p3) >= 0){
            hull.push(p1);
            hull.push(p2);
            hull.push(p3);
        }
        else{
            while(getDeterminate(p1,p2,p3) < 0)
            {
                p2 = p1;
                p1 = hull.top();
                hull.pop();

            }
            hull.push(p1);
            hull.push(p2);
            hull.push(p3);
        }
    }
}


void printHull(){

    fout << hull.size() << endl;
    fout << std::fixed;
    while(!hull.empty()){

        afisHull.push(hull.top());
        hull.pop();

    }
    while(!afisHull.empty()){
        fout << std::setprecision(6) << afisHull.top().first << " " << afisHull.top().second << endl;
        afisHull.pop();
    }
}
int main()
{
    scan();
    createHull();
    printHull();
    return 0;
}