This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#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; }