Cod sursa(job #2069554)

Utilizator blatulInstitutul de Arta Gastronomica blatul Data 18 noiembrie 2017 16:04:11
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;

#define eps 1e-12

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

class Point {

public:

    double x, y;

    Point(){}

    Point(double x, double y) {
        this->x = x;
        this->y = y;
    }


    bool operator< (const Point& a) const {

        if (abs(this->x - a.x) < eps)
            return this->y < a.y;

        return this->x < a.x;
    }

    friend istream& operator>> (istream& in, Point& a) {
        in >> a.x >> a.y;
        return in;
    }

    friend ostream& operator<< (ostream& out, Point& a) {
        out << a.x << " " << a.y;
        return out;
    }

};

double det(const Point& a, const Point& b, const Point& c) {

    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}

vector<Point> convexHull(const vector<Point>& points) {


    vector<Point> hull(points.size());

    int L = -1;

    for (int i = 0; i < points.size(); ++i) {
        while (L > 0 && det(hull[L - 1], hull[L], points[i]) < 0)
            L--;

        hull[++L] = points[i];
    }

    int l = L;
    L--;

    for (int i = points.size() - 1; i >= 0; --i) {
        while (L > l && det(hull[L - 1], hull[L], points[i]) < 0)
            L--;

        hull[++L] = points[i];
    }

    while (hull.size() != L)
        hull.pop_back();

    return hull;
}

int main() {

    int N;
    fin >> N;

    vector<Point> points;

    Point aux;
    while (fin >> aux) {
        points.push_back(aux);
    }

    sort(points.begin(), points.end());

    vector<Point> chull = convexHull(points);

    fout << chull.size() << "\n";
    for (auto& p: chull)
        fout << fixed << setprecision(7) << p << "\n";

    return 0;
}