Cod sursa(job #1977057)

Utilizator blatulInstitutul de Arta Gastronomica blatul Data 4 mai 2017 22:04:42
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 120002
#define eps 1e-12

ifstream fin("date.in");
ofstream fout("date.out");

class Point {

public:

    double x, y;

    Point(){}

    Point(double x, double y) {
        this->x = x;
        this->y = y;
    }

    bool operator< (const Point& A) const {

        if (abs(this->x - A.x) < eps)
            return this->y < A.y;

        return this->x < A.x;
    }

};

vector<Point> points;

double det(const Point& A, const Point& B, const Point& C) {

    return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
}

Point Hull[NMAX];
int ConvexHull(const int N) {

    int L = 0;

    for (int i = 1; i <= N; ++i) {
        while (L > 1 && det(Hull[L - 1], Hull[L], points[i]) <= 0)
            L--;

        Hull[++L] = points[i];
    }

    int l = L;

    for (int i = N; i >= 1; --i) {
        while (L > l && det(Hull[L - 1], Hull[L], points[i]) <= 0)
            L--;

        Hull[++L] = points[i];
    }

    L--;

    return L;
}

int main() {

    int N;

    fin >> N;

    points.resize(N + 2);

    for (int i = 1; i <= N; ++i)
        fin >> points[i].x >> points[i].y;

    sort(points.begin() + 1, points.begin() + N + 1);

    int nrP = ConvexHull(N);

    fout << nrP << "\n";
    for (int i = 1; i <= nrP; ++i)
        fout << fixed << setprecision(7) << Hull[i].x << " " << Hull[i].y << "\n";

    return 0;
}