Cod sursa(job #2256263)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 8 octombrie 2018 13:21:26
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.34 kb
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#include <assert.h>
#include <queue>
#include <chrono>
#include <memory>
#include <cstring>

using LL = long long;
using ULL = int long long;

const std::string _problemName = "infasuratoare";

#define USE_FILES

#ifdef USE_FILES

namespace std {
std::ifstream fin(_problemName + ".in");
std::ofstream fout(_problemName + ".out");
}

#define cin fin
#define cout fout
#endif

struct Point {
    double x, y;
};

double doubleSignedTriangleArea(const Point& p1, const Point& p2, const Point& p3) {
    return (p1.x - p3.x) * (p2.y - p3.y) - (p1.y - p3.y) * (p2.x - p3.x);
}

bool ccw(const Point& p1, const Point& p2, const Point& p3) {
    return doubleSignedTriangleArea(p1, p2, p3) > 0;
}

std::vector<Point> computeConvexHull(std::vector<Point>& points) {
    auto compareByX = [](const auto& p1, const auto& p2) {
        if (p1.x == p2.x) {
            // can't happen?
            return (p1.y < p2.y);
        }
        return p1.x < p2.x;
    };

    Point& bottomLeft = *std::min_element(
        points.begin(), 
        points.end(), 
        compareByX
    );

    // place minimum in the first position
    std::swap(*points.begin(), bottomLeft);

    auto compareByAngle = [bottomLeft] (const auto& p1, const auto& p2) {
        return ccw(bottomLeft, p1, p2);
    };

    std::sort(
        points.begin() + 1, 
        points.end(), 
        compareByAngle    
    );

    std::vector<Point> ch;

    auto breaksCcwProperty = [&ch](const Point& point) {
        const Point& beforeLast = ch[ch.size() - 2];
        const Point& last = ch[ch.size() - 1];

        return ch.size() >= 2 && !ccw(beforeLast, last, point);
    };

    // since bottomLeft is the first element of the `points` array, it will be inserted first
    for (const auto& point : points) {
        while (breaksCcwProperty(point)) {
            ch.pop_back();
        }
        ch.push_back(point);
    }

    return ch;
}

int main() {

    int n;
    std::cin >> n;

    std::vector<Point> points(n);

    for (auto& p : points) {
        std::cin >> p.x >> p.y;
    }

    auto ch = computeConvexHull(points);

    std::cout << ch.size() << '\n';
    for (const auto& p : ch) {
        std::cout << p.x << ' ' << p.y << '\n';
    }

    return 0;
}