test/src/integral_geom/convex_hull/CGL_4_A.test.cpp

• View this file on GitHub
• Last update: 2022-07-10 18:49:22+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_A

Depends on

• 凸包 (整数座標) (library/integral_geom/convex_hull.hpp)

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_A"

#include <cassert>
#include <iostream>
#include <iomanip>

#include "library/integral_geom/convex_hull.hpp"

using namespace suisen::integral_geometry;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(0);

    int n;
    std::cin >> n;

    std::vector<std::pair<long long, long long>> points(n);

    for (auto &[x, y] : points) std::cin >> x >> y;

    std::vector<int> ids = convex_hull(points);

    int amin = 0;
    for (int i = 1; i < int(ids.size()); ++i) {
        long long x0 = points[ids[amin]].first, y0 = points[ids[amin]].second;
        long long x1 = points[ids[i]].first, y1 = points[ids[i]].second;
        if (y1 < y0 or (y1 == y0 and x1 < x0)) {
            amin = i;
        }
    }

    std::cout << ids.size() << '\n';
    for (int i = 0; i < int(ids.size()); ++i) {
        auto [x, y] = points[ids[(amin + i) % ids.size()]];
        std::cout << x << ' ' << y << '\n';
    }
    return 0;
}

#line 1 "test/src/integral_geom/convex_hull/CGL_4_A.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_A"

#include <cassert>
#include <iostream>
#include <iomanip>

#line 1 "library/integral_geom/convex_hull.hpp"



#include <algorithm>
#include <numeric>
#include <vector>

namespace suisen::integral_geometry {
    template <typename PointType, typename MultipliedType = long long>
    std::vector<int> convex_hull(const std::vector<PointType> &points) {
        const int n = points.size();
        std::vector<int> sorted(n);
        std::iota(sorted.begin(), sorted.end(), 0);
        std::sort(sorted.begin(), sorted.end(), [&points](int i, int j) {
            const auto &[xi, yi] = points[i];
            const auto &[xj, yj] = points[j];
            return xi == xj ? yi < yj : xi < xj;
        });
        std::vector<int8_t> used(n, false);
        sorted.resize(2 * n - 1);
        std::copy(sorted.rbegin() + n, sorted.rend(), sorted.begin() + n);
        std::vector<int> res;
        res.reserve(n);
        int first = sorted[0], last = sorted[n - 1];
        auto isp_pos = [](MultipliedType x1, MultipliedType y1, MultipliedType x2, MultipliedType y2) -> bool {
            auto det = x1 * y2 - y1 * x2;
            return det > 0 or (det == 0 and x1 * x2 + y1 * y2 > 0);
        };
        for (int k : sorted) {
            if (k != first and used[k]) continue;
            for (int sz = res.size(); sz >= 2; --sz) {
                int i = res[sz - 2], j = res[sz - 1];
                if (j == last) break;
                const auto &[xi, yi] = points[i];
                const auto &[xj, yj] = points[j];
                const auto &[xk, yk] = points[k];
                auto ab_x = xj - xi, ab_y = yj - yi;
                auto bc_x = xk - xj, bc_y = yk - yj;
                if (isp_pos(ab_x, ab_y, bc_x, bc_y)) break;
                res.pop_back(), used[j] = false;
            }
            if (not used[k]) res.push_back(k);
            used[k] = true;
        }
        return res;
    }
} // namespace suisen::integral_geometry


#line 8 "test/src/integral_geom/convex_hull/CGL_4_A.test.cpp"

using namespace suisen::integral_geometry;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(0);

    int n;
    std::cin >> n;

    std::vector<std::pair<long long, long long>> points(n);

    for (auto &[x, y] : points) std::cin >> x >> y;

    std::vector<int> ids = convex_hull(points);

    int amin = 0;
    for (int i = 1; i < int(ids.size()); ++i) {
        long long x0 = points[ids[amin]].first, y0 = points[ids[amin]].second;
        long long x1 = points[ids[i]].first, y1 = points[ids[i]].second;
        if (y1 < y0 or (y1 == y0 and x1 < x0)) {
            amin = i;
        }
    }

    std::cout << ids.size() << '\n';
    for (int i = 0; i < int(ids.size()); ++i) {
        auto [x, y] = points[ids[(amin + i) % ids.size()]];
        std::cout << x << ' ' << y << '\n';
    }
    return 0;
}

Back to top page