This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub luzhiled1333/comp-library
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/4011 #include "src/cpp-template/header/int-alias.hpp" #include "src/cpp-template/header/rep.hpp" #include "src/cpp-template/header/size-alias.hpp" #include "src/geometry/Z2/class/point.hpp" #include "src/geometry/Z2/class/polygon.hpp" #include "src/geometry/Z2/class/segment.hpp" #include "src/geometry/Z2/compare/compare-yx.hpp" #include "src/geometry/Z2/segment-function/counterbalance-segments.hpp" #include "src/geometry/Z2/utility/polygon-to-segments.hpp" #include <iostream> #include <map> #include <vector> namespace luz { void main_() { usize n; std::cin >> n; using Z = i64; Z2::Segments< Z > segs; for ([[maybe_unused]] usize _: rep(0, n)) { Z2::Polygon< Z > triangle(3); for (usize i: rep(0, 3)) { Z x, y; std::cin >> x >> y; triangle[i] = Z2::Point< Z >(x, y); } auto edges = polygon_to_segments(triangle); for (auto &edge: edges) segs.emplace_back(edge); } auto edges = counterbalance_segments(segs); using Point = Z2::Point< Z >; std::map< Point, Point, Z2::CompareYX< Z > > mp; constexpr Z inf = 1e9 + 5; Point pt(inf, inf); for (auto &edge: edges) { Point from = edge.p0(); Point to = edge.p1(); mp[from] = to; Z2::CompareYX< Z > comp; if (comp(from, pt)) pt = from; } for ([[maybe_unused]] usize _: rep(0, edges.size())) { std::cout << pt.x() << " " << pt.y() << std::endl; pt = mp[pt]; } } } // namespace luz int main() { luz::main_(); }
#line 1 "test/aoj/4011.test.cpp" // verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/4011 #line 2 "src/cpp-template/header/int-alias.hpp" #include <cstdint> namespace luz { using i32 = std::int32_t; using i64 = std::int64_t; using i128 = __int128_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using u128 = __uint128_t; } // namespace luz #line 2 "src/cpp-template/header/rep.hpp" #line 2 "src/cpp-template/header/size-alias.hpp" #include <cstddef> namespace luz { using isize = std::ptrdiff_t; using usize = std::size_t; } // namespace luz #line 4 "src/cpp-template/header/rep.hpp" #include <algorithm> namespace luz { struct rep { struct itr { usize i; constexpr itr(const usize i) noexcept: i(i) {} void operator++() noexcept { ++i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rep(const usize f, const usize l) noexcept : f(std::min(f, l)), l(l) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; struct rrep { struct itr { usize i; constexpr itr(const usize i) noexcept: i(i) {} void operator++() noexcept { --i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rrep(const usize f, const usize l) noexcept : f(l - 1), l(std::min(f, l) - 1) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; } // namespace luz #line 2 "src/geometry/Z2/class/point.hpp" #line 2 "src/geometry/Z2/class/vector.hpp" #include <vector> namespace luz::Z2 { template < typename Z > class Vector { Z x_, y_; public: Vector(): x_(0), y_(0) {} Vector(Z x, Z y): x_(x), y_(y) {} Z x() const { return x_; } Z y() const { return y_; } bool operator==(const Vector &v) const { return x_ == v.x_ and y_ == v.y_; } bool operator!=(const Vector &v) const { return x_ != v.x_ or y_ != v.y_; } Vector &operator+=(const Vector &v) { x_ += v.x_; y_ += v.y_; return *this; } Vector &operator-=(const Vector &v) { x_ -= v.x_; y_ -= v.y_; return *this; } Vector operator+(const Vector &v) const { return Vector(*this) += v; } Vector operator-(const Vector &v) const { return Vector(*this) -= v; } Vector operator+() const { return *this; } Vector operator-() const { return Vector() - *this; } }; template < typename Z > using Vectors = std::vector< Vector< Z > >; } // namespace luz::Z2 #line 4 "src/geometry/Z2/class/point.hpp" #line 6 "src/geometry/Z2/class/point.hpp" namespace luz::Z2 { template < typename Z > using Point = Vector< Z >; template < typename Z > using Points = std::vector< Point< Z > >; } // namespace luz::Z2 #line 2 "src/geometry/Z2/class/polygon.hpp" #line 4 "src/geometry/Z2/class/polygon.hpp" #line 6 "src/geometry/Z2/class/polygon.hpp" namespace luz::Z2 { template < typename Z > using Polygon = std::vector< Point< Z > >; template < typename Z > using Polygons = std::vector< Polygon< Z > >; } // namespace luz::Z2 #line 2 "src/geometry/Z2/class/segment.hpp" #line 4 "src/geometry/Z2/class/segment.hpp" #include <cassert> #line 7 "src/geometry/Z2/class/segment.hpp" namespace luz::Z2 { template < typename Z > class Segment { Point< Z > p0_, p1_; public: Segment() = default; Segment(Point< Z > p0, Point< Z > p1): p0_(p0), p1_(p1) { assert(p0 != p1); } Point< Z > p0() const { return p0_; } Point< Z > p1() const { return p1_; } }; template < typename Z > using Segments = std::vector< Segment< Z > >; } // namespace luz::Z2 #line 2 "src/geometry/Z2/compare/compare-yx.hpp" #line 4 "src/geometry/Z2/compare/compare-yx.hpp" namespace luz::Z2 { template < typename Z > class CompareYX { public: bool operator()(const Vector< Z > &v0, const Vector< Z > &v1) const noexcept { if (v0.y() != v1.y()) return v0.y() < v1.y(); return v0.x() < v1.x(); } }; } // namespace luz::Z2 #line 2 "src/geometry/Z2/segment-function/counterbalance-segments.hpp" #line 2 "src/geometry/Z2/compare/compare-xy.hpp" #line 4 "src/geometry/Z2/compare/compare-xy.hpp" namespace luz::Z2 { template < typename Z > class CompareXY { public: bool operator()(const Vector< Z > &v0, const Vector< Z > &v1) const noexcept { if (v0.x() != v1.x()) return v0.x() < v1.x(); return v0.y() < v1.y(); } }; } // namespace luz::Z2 #line 2 "src/geometry/Z2/normalize/line-normalize.hpp" #line 2 "src/geometry/Z2/class/line.hpp" #line 4 "src/geometry/Z2/class/line.hpp" #line 7 "src/geometry/Z2/class/line.hpp" namespace luz::Z2 { template < typename Z > class Line { Point< Z > p0_, p1_; public: Line() = default; Line(Point< Z > p0, Point< Z > p1): p0_(p0), p1_(p1) { assert(p0 != p1); } Point< Z > p0() const { return p0_; } Point< Z > p1() const { return p1_; } }; template < typename Z > using Lines = std::vector< Line< Z > >; } // namespace luz::Z2 #line 4 "src/geometry/Z2/normalize/line-normalize.hpp" #line 6 "src/geometry/Z2/normalize/line-normalize.hpp" #include <numeric> #include <tuple> #include <type_traits> namespace luz::Z2 { template < typename Z > std::tuple< Z, Z, Z > normalize_l(const Line< Z > &l) { static_assert(std::is_signed< Z >::value == true); Z a = l.p1().y() - l.p0().y(); Z b = l.p0().x() - l.p1().x(); { Z g = std::gcd(a, b); a /= g; b /= g; } Z c = a * l.p0().x() + b * l.p0().y(); std::tuple< Z, Z, Z > p(+a, +b, +c), m(-a, -b, -c); return std::max(p, m); } } // namespace luz::Z2 #line 2 "src/geometry/Z2/operation/ccw.hpp" #line 2 "src/geometry/Z2/constants/ccw-constants.hpp" namespace luz::Z2::constants::ccw { constexpr i32 COUNTER_CLOCKWISE = +1; constexpr i32 CLOCKWISE = -1; constexpr i32 ONLINE_BACK = +2; // c-a-b constexpr i32 ONLINE_FRONT = -2; // a-b-c constexpr i32 ON_SEGMENT = 0; // a-c-b } // namespace luz::Z2::constants::ccw #line 2 "src/geometry/Z2/operation/cross-product.hpp" #line 4 "src/geometry/Z2/operation/cross-product.hpp" namespace luz::Z2 { template < typename Z > Z cross_product(const Vector< Z > &a, const Vector< Z > &b) { return a.x() * b.y() - a.y() * b.x(); } } // namespace luz::Z2 #line 2 "src/geometry/Z2/operation/inner-product.hpp" #line 4 "src/geometry/Z2/operation/inner-product.hpp" namespace luz::Z2 { template < typename Z > Z inner_product(const Vector< Z > &a, const Vector< Z > &b) { return a.x() * b.x() + a.y() * b.y(); } } // namespace luz::Z2 #line 2 "src/geometry/Z2/operation/square-norm.hpp" #line 2 "src/geometry/Z2/operation/square.hpp" namespace luz::Z2 { template < typename Z > Z square(const Z x) { return x * x; } } // namespace luz::Z2 #line 5 "src/geometry/Z2/operation/square-norm.hpp" namespace luz::Z2 { template < typename Z > Z square_norm(Vector< Z > v) { return square(v.x()) + square(v.y()); } } // namespace luz::Z2 #line 9 "src/geometry/Z2/operation/ccw.hpp" namespace luz::Z2::impl_ccw { using namespace constants::ccw; template < typename Z > i32 ccw(const Vector< Z > &a, Vector< Z > b, Vector< Z > c) { b -= a; c -= a; Z cp = cross_product(b, c); if (cp > 0) return COUNTER_CLOCKWISE; if (cp < 0) return CLOCKWISE; if (inner_product(b, c) < 0) return ONLINE_BACK; if (square_norm(b) < square_norm(c)) return ONLINE_FRONT; return ON_SEGMENT; } } // namespace luz::Z2::impl_ccw namespace luz::Z2 { template < typename Z > i32 ccw(const Vector< Z > &a, const Vector< Z > &b, const Vector< Z > &c) { return impl_ccw::ccw(a, b, c); } } // namespace luz::Z2 #line 2 "src/geometry/Z2/utility/next-idx.hpp" #line 4 "src/geometry/Z2/utility/next-idx.hpp" namespace luz::Z2 { inline usize next_idx(usize idx, usize size) { return idx + 1 == size ? 0 : idx + 1; } } // namespace luz::Z2 #line 2 "src/sequence/compression.hpp" #line 5 "src/sequence/compression.hpp" #line 8 "src/sequence/compression.hpp" #include <functional> #line 10 "src/sequence/compression.hpp" namespace luz { template < class T, class Compare = std::less< T > > class Compressor { std::vector< T > vs; std::vector< T > zip; std::vector< usize > ziped_vs; public: explicit Compressor(std::vector< T > vs) : vs(vs), zip(vs), ziped_vs(vs.size()) { std::sort(zip.begin(), zip.end(), Compare()); zip.erase(std::unique(zip.begin(), zip.end()), zip.end()); for (usize i: rep(0, vs.size())) { ziped_vs[i] = compress(vs[i]); } } std::vector< usize > compressed_vector() const { return ziped_vs; } usize compress(T v) const { auto iter = std::lower_bound(zip.begin(), zip.end(), v); assert(*iter == v); return iter - zip.begin(); } T expand(usize i) const { assert(i < zip.size()); return zip[i]; } }; } // namespace luz #line 12 "src/geometry/Z2/segment-function/counterbalance-segments.hpp" #include <cmath> #line 15 "src/geometry/Z2/segment-function/counterbalance-segments.hpp" #include <utility> #line 17 "src/geometry/Z2/segment-function/counterbalance-segments.hpp" namespace luz::Z2 { template < typename Z > Segments< Z > counterbalance_segments( const Segments< Z > &segments) { usize n = segments.size(); std::vector< std::tuple< Z, Z, Z > > normalized_lines(n); for (usize i: rep(0, n)) { normalized_lines[i] = normalize_l(Line(segments[i].p0(), segments[i].p1())); } Compressor compressor(normalized_lines); std::vector< usize > line_idxs = compressor.compressed_vector(); usize line_count = (*std::max_element(line_idxs.begin(), line_idxs.end())) + 1; using event_type = std::pair< Point< Z >, i32 >; std::vector< std::vector< event_type > > events_each_line( line_count); for (usize i: rep(0, n)) { usize l_idx = line_idxs[i]; events_each_line[l_idx].emplace_back(segments[i].p0(), +1); events_each_line[l_idx].emplace_back(segments[i].p1(), -1); } auto cmp = [](const event_type &e0, const event_type &e1) { CompareXY< Z > comp; if (e0.first != e1.first) return comp(e0.first, e1.first); return e0.second < e1.second; }; Segments< Z > result; for (auto &events: events_each_line) { std::sort(events.begin(), events.end(), cmp); for (usize i: rep(1, events.size())) { i32 prev = events[i - 1].second; events[i].second += prev; if (events[i - 1].first == events[i].first) continue; if (std::abs(prev) != 1) continue; Point< Z > from = events[i - 1].first; Point< Z > to = events[i].first; if (prev == -1) std::swap(from, to); Segment< Z > seg(from, to); if (not result.empty()) { Segment< Z > prev_seg = result.back(); Vector< Z > a = prev_seg.p0(), b = prev_seg.p1(); Vector< Z > c = seg.p0(), d = seg.p1(); if (b == c and std::abs(ccw(a, c, d)) != 1) { seg = Segment(a, d); result.pop_back(); } if (a == d and std::abs(ccw(c, a, b)) != 1) { seg = Segment(c, b); result.pop_back(); } } result.emplace_back(seg); } } return result; } } // namespace luz::Z2 #line 2 "src/geometry/Z2/utility/polygon-to-segments.hpp" #line 7 "src/geometry/Z2/utility/polygon-to-segments.hpp" namespace luz::Z2 { template < typename Z > Segments< Z > polygon_to_segments(const Polygon< Z > &poly) { usize n = poly.size(); Segments< Z > segments(n); for (usize i: rep(0, n)) { segments[i] = Segment< Z >(poly[i], poly[next_idx(i, n)]); } return segments; } } // namespace luz::Z2 #line 12 "test/aoj/4011.test.cpp" #include <iostream> #include <map> #line 16 "test/aoj/4011.test.cpp" namespace luz { void main_() { usize n; std::cin >> n; using Z = i64; Z2::Segments< Z > segs; for ([[maybe_unused]] usize _: rep(0, n)) { Z2::Polygon< Z > triangle(3); for (usize i: rep(0, 3)) { Z x, y; std::cin >> x >> y; triangle[i] = Z2::Point< Z >(x, y); } auto edges = polygon_to_segments(triangle); for (auto &edge: edges) segs.emplace_back(edge); } auto edges = counterbalance_segments(segs); using Point = Z2::Point< Z >; std::map< Point, Point, Z2::CompareYX< Z > > mp; constexpr Z inf = 1e9 + 5; Point pt(inf, inf); for (auto &edge: edges) { Point from = edge.p0(); Point to = edge.p1(); mp[from] = to; Z2::CompareYX< Z > comp; if (comp(from, pt)) pt = from; } for ([[maybe_unused]] usize _: rep(0, edges.size())) { std::cout << pt.x() << " " << pt.y() << std::endl; pt = mp[pt]; } } } // namespace luz int main() { luz::main_(); }