Cod sursa(job #1556205)

Utilizator andreiiiiPopa Andrei andreiiii Data 24 decembrie 2015 12:54:00
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 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];

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

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


struct cmp {
    bool operator()(const Point& a, const Point& b) const {
        return crossProduct(A[1], a, b) > 0;
    }
};

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 || 
                (abs(A[i].x - A[1].x) < eps && 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]) < 0) {
            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();
}