Cod sursa(job #1165638)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 2 aprilie 2014 19:56:57
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.28 kb
#include <cmath>

#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>

#define x first
#define y second

using namespace std;

typedef pair<double, double> Point;

const double EPS = 1e-9;

class ConvexHull {
  public:
    ConvexHull(const vector<Point> &points):
      hull(set< pair<double, Point> >()),
      center(Point(0.0, 0.0)) {
        for (int i = 0; i < 3; ++i) {
            center.x += points[i].x;
            center.y += points[i].y;
        }
        center.x /= 3.0;
        center.y /= 3.0;
        for (int i = 0; i < 3; ++i)
            hull.insert(make_pair(atan2(points[i].y - center.y, points[i].x - center.x), points[i]));
        for (int i = 3; i < int(points.size()); ++i)
            Insert(points[i]);
    }

    void Insert(const Point &p) {
        double alpha = atan2(p.y - center.y, p.x - center.x);
        set< pair<double, Point> >::iterator after = hull.lower_bound(make_pair(alpha, p)), before;
        if (after == hull.end())
            after = hull.begin();
        before = Previous(after);
        if (Det(before->second, p, after->second) < EPS)
            return;
        while (int(hull.size()) > 2 && Det(p, after->second, Next(after)->second) < EPS) {
            hull.erase(after);
            after = hull.lower_bound(make_pair(alpha, p));
            if (after == hull.end())
                after = hull.begin();
        }
        before = Previous(after);
        while (int(hull.size()) > 2 && Det(Previous(before)->second, before->second, p) < EPS) {
            hull.erase(before);
            before = hull.lower_bound(make_pair(alpha, p));
            if (before == hull.begin())
                before = hull.end();
            --before;
        }
        hull.insert(make_pair(alpha, p));
    }

    vector<Point> GetHull() const {
        vector<Point> points;
        for (set< pair<double, Point> >::const_iterator p = hull.begin(); p != hull.end(); ++p)
            points.push_back(p->second);
        return points;
    }

    static double Det(const Point &a, const Point &b, const Point &c) {
        return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    }

  private:
    set< pair<double, Point> > hull;
    Point center;

    set< pair<double, Point> >::iterator Next(set< pair<double, Point> >::iterator p) const {
        ++p;
        if (p == hull.end())
            p = hull.begin();
        return p;
    }

    set< pair<double, Point> >::iterator Previous(set< pair<double, Point> >::iterator p) const {
        if (p == hull.begin())
            p = hull.end();
        --p;
        return p;
    }
};

vector<Point> Points, Hull;

void Solve() {
    Hull = ConvexHull(Points).GetHull();
}

void Read() {
    ifstream cin("infasuratoare.in");
    int n;
    cin >> n;
    Points = vector<Point>(n);
    for (int i = 0; i < n; ++i)
        cin >> Points[i].x >> Points[i].y;
    cin.close();
}

void Print() {
    ofstream cout("infasuratoare.out");
    cout << int(Hull.size()) << "\n";
    for (int i = 0; i < int(Hull.size()); ++i)
        cout << fixed << setprecision(7) << Hull[i].x << " " << Hull[i].y << "\n";
    cout.close();
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}