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/atcoder/abc259_d.test.cpp

Depends on

Code

// verification-helper: PROBLEM https://atcoder.jp/contests/abc259/tasks/abc259_d

#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/data-structure/disjoint-set-union.hpp"
#include "src/geometry/Z2/class/circle.hpp"
#include "src/geometry/Z2/class/point.hpp"
#include "src/geometry/Z2/intersect/is-intersect-circle-circle.hpp"
#include "src/geometry/Z2/intersect/is-intersect-point-circle.hpp"

#include <iostream>

namespace luz {

  void main_() {
    usize n;
    std::cin >> n;

    i64 sx, sy, tx, ty;
    std::cin >> sx >> sy >> tx >> ty;

    using namespace Z2;
    Point< i64 > s(sx, sy), t(tx, ty);

    Circles< i64 > cs;
    for ([[maybe_unused]] usize _: rep(0, n)) {
      i64 x, y, r;
      std::cin >> x >> y >> r;

      cs.emplace_back(Point< i64 >(x, y), r);
    }

    DisjointSetUnion uf(n + 2);
    usize s_idx = n, t_idx = n + 1;

    for (usize i: rep(0, n)) {
      if (is_intersect_pc(s, cs[i])) {
        uf.merge(s_idx, i);
      }
      if (is_intersect_pc(t, cs[i])) {
        uf.merge(i, t_idx);
      }
    }

    for (usize i: rep(0, n))
      for (usize j: rep(0, i)) {
        if (is_intersect_cc(cs[i], cs[j])) {
          uf.merge(i, j);
        }
      }

    std::cout << (uf.same(s_idx, t_idx) ? "Yes" : "No") << std::endl;
  }

} // namespace luz

int main() {
  luz::main_();
}
#line 1 "test/atcoder/abc259_d.test.cpp"
// verification-helper: PROBLEM https://atcoder.jp/contests/abc259/tasks/abc259_d

#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/data-structure/disjoint-set-union.hpp"

#line 5 "src/data-structure/disjoint-set-union.hpp"

#line 7 "src/data-structure/disjoint-set-union.hpp"
#include <cassert>
#include <vector>

namespace luz {

  class DisjointSetUnion {
    usize n;

    // vals[v] :=
    //   if v is root node: -1 * component size
    //   otherwise: parent node
    std::vector< isize > vals;

    void bound_check(usize v) const {
      assert(v < n);
    }

    usize impl_leader(usize v) {
      if (vals[v] < 0) return v;
      return vals[v] = leader(vals[v]);
    }

   public:
    DisjointSetUnion() = default;
    explicit DisjointSetUnion(usize n): n(n), vals(n, -1) {}

    usize size() const {
      return n;
    }

    usize leader(usize v) {
      bound_check(v);
      return impl_leader(v);
    }

    bool same(usize u, usize v) {
      bound_check(u), bound_check(v);
      return impl_leader(u) == impl_leader(v);
    }

    usize merge(usize u, usize v) {
      bound_check(u);
      bound_check(v);

      isize x = impl_leader(u);
      isize y = impl_leader(v);
      if (x == y) return x;
      if (-vals[x] < -vals[y]) std::swap(x, y);
      vals[x] += vals[y];
      vals[y] = x;
      return x;
    }

    usize group_size(usize v) {
      bound_check(v);
      return -vals[impl_leader(v)];
    }

    std::vector< std::vector< usize > > groups() {
      std::vector< std::vector< usize > > result(n);

      std::vector< usize > leaders(n), g_sizes(n);
      for (usize v: rep(0, n)) {
        leaders[v] = impl_leader(v);
        g_sizes[leaders[v]]++;
      }
      for (usize v: rep(0, n)) {
        result[v].reserve(g_sizes[v]);
      }
      for (usize v: rep(0, n)) {
        result[leaders[v]].emplace_back(v);
      }

      auto empty_check = [](const std::vector< usize > &vs) {
        return vs.empty();
      };
      result.erase(
          std::remove_if(result.begin(), result.end(), empty_check),
          result.end());

      return result;
    }
  };

} // namespace luz
#line 2 "src/geometry/Z2/class/circle.hpp"

#line 2 "src/geometry/Z2/class/point.hpp"

#line 2 "src/geometry/Z2/class/vector.hpp"

#line 4 "src/geometry/Z2/class/vector.hpp"

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 4 "src/geometry/Z2/class/circle.hpp"

#line 6 "src/geometry/Z2/class/circle.hpp"

namespace luz::Z2 {

  template < typename Z >
  class Circle {

    Point< Z > o_;
    Z r_;

   public:
    Circle(): o_(0, 0), r_(0) {}

    Circle(Point< Z > o, Z r): o_(o), r_(r) {
      assert(r >= 0);
    }

    Point< Z > center() const {
      return o_;
    }

    Z r() const {
      return r_;
    }
  };

  template < typename Z >
  using Circles = std::vector< Circle< Z > >;

} // namespace luz::Z2
#line 2 "src/geometry/Z2/intersect/is-intersect-circle-circle.hpp"

#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 7 "src/geometry/Z2/intersect/is-intersect-circle-circle.hpp"

#include <utility>

namespace luz::Z2 {

  template < typename Z >
  bool is_intersect_cc(Circle< Z > c0, Circle< Z > c1) {
    if (c0.r() > c1.r()) std::swap(c0, c1);

    Z sq_dist = square_norm(c0.center() - c1.center());

    if (sq_dist < square(c1.r() - c0.r())) return false;
    if (square(c1.r() + c0.r()) < sq_dist) return false;
    return true;
  }

} // namespace luz::Z2
#line 2 "src/geometry/Z2/intersect/is-intersect-point-circle.hpp"

#line 6 "src/geometry/Z2/intersect/is-intersect-point-circle.hpp"

namespace luz::Z2 {

  template < typename Z >
  bool is_intersect_pc(Point< Z > p, Circle< Z > c) {
    Z sq_norm = square_norm(c.center() - p);
    return sq_norm == square(c.r());
  }

} // namespace luz::Z2
#line 11 "test/atcoder/abc259_d.test.cpp"

#include <iostream>

namespace luz {

  void main_() {
    usize n;
    std::cin >> n;

    i64 sx, sy, tx, ty;
    std::cin >> sx >> sy >> tx >> ty;

    using namespace Z2;
    Point< i64 > s(sx, sy), t(tx, ty);

    Circles< i64 > cs;
    for ([[maybe_unused]] usize _: rep(0, n)) {
      i64 x, y, r;
      std::cin >> x >> y >> r;

      cs.emplace_back(Point< i64 >(x, y), r);
    }

    DisjointSetUnion uf(n + 2);
    usize s_idx = n, t_idx = n + 1;

    for (usize i: rep(0, n)) {
      if (is_intersect_pc(s, cs[i])) {
        uf.merge(s_idx, i);
      }
      if (is_intersect_pc(t, cs[i])) {
        uf.merge(i, t_idx);
      }
    }

    for (usize i: rep(0, n))
      for (usize j: rep(0, i)) {
        if (is_intersect_cc(cs[i], cs[j])) {
          uf.merge(i, j);
        }
      }

    std::cout << (uf.same(s_idx, t_idx) ? "Yes" : "No") << std::endl;
  }

} // namespace luz

int main() {
  luz::main_();
}
Back to top page