This documentation is automatically generated by online-judge-tools/verification-helper
// 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_();
}