comp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub luzhiled1333/comp-library

:heavy_check_mark: test/aoj/4011.test.cpp

Depends on

Code

// 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_();
}
Back to top page