Cod sursa(job #1556180)

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

struct Point {
    double x, y;
    double angle;
};
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 {
        if (abs(a.angle - b.angle) < eps) {
            return a.x < b.x;
        } else {
            return a.angle < b.angle;
        }
    }
};

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

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

    int n;
    fin >> n;

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

    for (int i = 2; i <= n; ++i) {
        if (A[i].x < A[1].x || 
                (A[i].x == A[1].x && A[i].y < A[1].y)) {
            swap(A[1], A[i]);
        }
    }
    for (int i = 2; i <= n; ++i) {
        A[i].angle = atan2(A[i].y - A[1].y, A[i].x - A[1].x);
    }
    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].x << ' ' << B[i].y << '\n';
    }

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