Cod sursa(job #1556178)

Utilizator andreiiiiPopa Andrei andreiiii Data 24 decembrie 2015 12:32:08
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <algorithm>
#include <fstream>
#include <cmath>
#include <iomanip>
using namespace std;

typedef pair<double, double> Point;
const int NMAX = 120005;
const double eps = 1e-12;
Point A[NMAX], B[NMAX];

struct cmp {
    bool operator()(const Point& a, const Point& b) const {
        double a1 = atan2(a.second - A[1].second, a.first - A[1].first);
        double a2 = atan2(b.second - A[1].second, b.first - A[1].first);
        if (abs(a1 - a2) < eps) {
            return a.first < b.first;
        } else {
            return a1 < a2;
        }
    }
};

double crossProduct(const Point &o, const Point& a,
        const Point &b) {
    return (a.first - o.first) * (b.second - o.second) -
        (a.second - o.second) * (b.first - o.first);
}

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

    int n;
    fin >> n;

    for (int i = 1; i <= n; ++i) {
        fin >> A[i].first >> A[i].second;
    }

    for (int i = 2; i <= n; ++i) {
        if (A[i].first < A[1].first || 
                (A[i].first == A[1].first && A[i].second < A[1].second)) {
            swap(A[1], A[i]);
        }
    }
    sort(A + 2, A + n + 1, cmp());

    int k = 1;
    B[1] = A[1];
    for (int i = 2; i <= n; ++i) {
        while (k > 1 && crossProduct(B[k - 1], B[k], A[i]) < eps) {
            k--;
        }
        B[++k] = A[i];
    }

    fout << setprecision(12) << fixed;
    fout << k << '\n';
    for (int i = 1; i <= k; ++i) {
        fout << B[i].first << ' ' << B[i].second << '\n';
    }

    fin.close();
    fout.close();
}