Cod sursa(job #756590)

Utilizator BitOneSAlexandru BitOne Data 9 iunie 2012 22:20:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <cmath>
#include <vector>
#include <fstream>
#include <iomanip>
#include <cstdlib>
#include <iterator>
#include <algorithm>

using namespace std;
typedef pair<double, double> pr;
const double error=1e-12;

pr p0;
vector<pr> v, ConvexHull;

namespace std {
    inline istream& operator>>(istream& in, pr& x) {in>>x.first>>x.second; return in;}
    inline ostream& operator<<(ostream& out, const pr& x) {out<<fixed<<setprecision(12)<<x.first<<' '<<x.second; return out;}
    inline pr operator-(const pr& x, const pr& y) {pr z(x.first-y.first, x.second-y.second); return z;}
};
inline double crossProduct(const pr& x, const pr& y) {return x.first*y.second - x.second*y.first;}
inline bool cmp(const pr& x, const pr& y) {return crossProduct(x-p0, y-p0) < error;}

int main()
{
     pr p;
    int N, i, j;

    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");

    in>>N>>p0;
    for(i=1; i < N; ++i)
    {
        in>>p;
        if(p.first < p0.first || (p.first == p0.first && p.second < p0.second))
        {
            v.push_back(p0);
            p0=p;
        }
        else v.push_back(p);
    }
    sort(v.begin(), v.end(), cmp);
    ConvexHull.push_back(p0);
    ConvexHull.push_back(v[0]);
    ConvexHull.push_back(v[1]);
    for(i=2, N-=1; i < N; ++i)
    {
        for(j=ConvexHull.size()-1; j && crossProduct(v[i]-ConvexHull[j], ConvexHull[j-1] - ConvexHull[j]) >= error; --j)
            ConvexHull.pop_back();
        ConvexHull.push_back(v[i]);
    }
    out<<ConvexHull.size()<<'\n';
    copy(ConvexHull.rbegin(), ConvexHull.rend(), ostream_iterator<pr>(out, "\n"));
    return EXIT_SUCCESS;
}