Cod sursa(job #1178396)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 26 aprilie 2014 15:20:20
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 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;

inline 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);
}

class Compare {
  public:
    static vector<double> alpha;

    bool operator()(const int a, const int b) const {
        return alpha[a] < alpha[b];
    }
};

vector<double> Compare::alpha = vector<double>();

vector<int> ConvexHull(const vector<Point> &points) {
    int n = int(points.size());
    int center = 0;
    for (int i = 1; i < n; ++i)
        if (points[i] < points[center])
            center = i;
    vector<double> alpha = vector<double>(n);
    for (int i = 0; i < n; ++i)
        alpha[i] = atan2(points[i].y - points[center].y, points[i].x - points[center].x);
    vector<int> index = vector<int>(n);
    for (int i = 0; i < n; ++i)
        index[i] = i;
    swap(index[0], index[center]);
    Compare::alpha = alpha;
    sort(index.begin() + 1, index.end(), Compare());
    vector<int> hull;
    hull.push_back(index[0]);
    hull.push_back(index[1]);
    for (int i = 2; i < n; ++i) {
        while (int(hull.size()) > 1 && Det(points[hull[int(hull.size()) - 2]], points[hull.back()], points[index[i]]) < -EPS)
            hull.pop_back();
        hull.push_back(index[i]);
    }
    return hull;
}

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<int> hull = ConvexHull(points);
    out << int(hull.size()) << "\n";
    for (int i = 0; i < int(hull.size()); ++i)
        out << fixed << setprecision(9) << points[hull[i]].x << " " << points[hull[i]].y << "\n";
    in.close();
    out.close();
    return 0;
}