Cod sursa(job #1957697)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 7 aprilie 2017 18:37:05
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.04 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(Alpha(points[i]), points[i]));
        for (int i = 3; i < int(points.size()); ++i)
            Insert(points[i]);
    }
 
    void Insert(const Point &point) {
        double alpha = Alpha(point);
        set< pair<double, Point> >::iterator p = hull.lower_bound(make_pair(alpha, point));
        if (p == hull.end())
            p = hull.begin();
        if (Det(Previous(p)->second, point, p->second) < EPS)
            return;
        while (int(hull.size()) > 1 && Det(point, p->second, Next(p)->second) < EPS) {
            hull.erase(p);
            p = hull.lower_bound(make_pair(alpha, point));
            if (p == hull.end())
                p = hull.begin();
        }
        p = Previous(p);
        while (int(hull.size()) > 1 && Det(Previous(p)->second, p->second, point) < EPS) {
            hull.erase(p);
            p = hull.lower_bound(make_pair(alpha, point));
            if (p == hull.end())
                p = hull.begin();
            p = Previous(p);
        }
        hull.insert(make_pair(alpha, point));
    }
 
    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;
    }
 
  private:
    set< pair<double, Point> > hull;
    Point center;
 
    static double Det(const Point &a, const Point &b, const Point &c) {
        return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
    }
 
    double Alpha(const Point &p) const {
        return atan2(p.y - center.y, p.x - center.x);
    }
 
    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;
    }
};
 
int main() {
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");
    int n;
    in >> n;
    vector<Point> points = vector<Point>(n);
    for (int i = 0; i < n; ++i)
        in >> points[i].x >> points[i].y;
    vector<Point> hull = ConvexHull(points).GetHull();
    out << int(hull.size()) << "\n";
    for (int i = 0; i < int(hull.size()); ++i)
        out << fixed << setprecision(9) << hull[i].x << " " << hull[i].y << "\n";
    in.close();
    out.close();
    return 0;
}