P5525 [Ynoi2012] WC2016 充满了失望

circle.cpp

// long double

#define NDEBUG

#include <algorithm>
#include <iostream>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <optional>
#include <queue>
#include <set>
#include <string>
#include <vector>

using i64 = long long;
using i128 = __int128_t;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = unsigned __int128_t;
using f64 = double;
using f128 = long double;

void set_io([[maybe_unused]] std::string name)
{
#ifndef NO_FREOPEN
  freopen((name + ".in").c_str(), "r", stdin);
  freopen((name + ".out").c_str(), "w", stdout);
#endif
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

constexpr f128 eps = 1e-6;

template <typename T>
struct vec
{
  T x, y;

  vec() : x(0), y(0) {}
  vec(T x, T y) : x(x), y(y) {}
  template <typename S>
  vec(vec<S> v) : x(v.x), y(v.y) {}

  bool operator<(const vec &v) const
  {
    if (x != v.x) return x < v.x;
    else return y < v.y;
  }

  vec operator-() const { return {-x, -y}; }

  vec operator+(const vec &v) const { return {x + v.x, y + v.y}; }
  vec operator-(const vec &v) const { return {x - v.x, y - v.y}; }
  vec operator*(T v) const { return {x * v, y * v}; }
  vec operator/(T v) const { return {x / v, y / v}; }

  T det(const vec &v) const { return x * v.y - y * v.x; }

  f128 norm() const { return std::hypot(x, y); }
  vec<f128> unit() const { return vec<f128>{*this} / norm(); }

  bool operator==(const vec &v) const { return x == v.x && y == v.y; }
  bool almost_same(const vec &v) const { return std::max(std::fabs(x - v.x), std::fabs(y - v.y)) <= eps; }
};

template <typename T>
struct line
{
  T a, b, c;
  line(vec<T> A, vec<T> B) : a(B.y - A.y), b(A.x - B.x), c(-a * A.x - b * A.y) {}

  vec<f128> vec_at_x(T x)
  {
    assert(b != 0);
    return {(f128)x, (f128)(-a * x - c) / b};
  }

  T calc(const vec<T> &v)
  {
    return a * v.x + b * v.y + c;
  }

  f128 distance(const vec<T> &v)
  {
    return std::fabs((f128)calc(v) / std::sqrt((f128)a * a + (f128)b * b));
  }
};

vec<f128> intersection(const line<f128> &l1, const line<f128> &l2) 
{
  f128 det = l1.a * l2.b - l2.a * l1.b;
  assert(det != 0);
  f128 x = l1.b * l2.c - l2.b * l1.c;
  f128 y = l1.c * l2.a - l2.c * l1.a;
  return {x / det, y / det};
}

template <typename T>
std::vector<int> get_convex(const std::vector<vec<T>> &points)
{
  int n = points.size();
  if (n == 1) return {0};
  if (n == 2) return {0, 1};

  auto check = [&](int i, int j, int k)
  {
    auto dij = points[j] - points[i];
    auto dkj = points[k] - points[j];
    return dij.det(dkj) > 0;
  };

  auto calc = [&](int start, int stop, int step)
  {
    std::vector<int> res;
    for (int i = start; i != stop; i += step) {
      while (res.size() >= 2 && !check(res.end()[-2], res.end()[-1], i)) {
        res.pop_back();
      }
      res.emplace_back(i);
    }
    return res;
  };

  return calc(0, n, 1);
}

template <typename T, typename X>
struct LinearFunc
{
  T k, b;
  X s;
  LinearFunc(T k, T b, X s) : k(k), b(b), s(s) 
  {
    assert(std::fabs(k.x) > eps || std::fabs(k.y) > eps);
  }

  T calc(X x) const 
  { 
    assert(s <= x);
    return k * x + b; 
  }
};

struct Compare
{
  using is_transparent = void;

  template <typename T, typename X>
  bool operator()(const std::pair<LinearFunc<T, X>, int> &a, const std::pair<LinearFunc<T, X>, int> &b) const
  {
    X x = std::max(a.first.s, b.first.s);
    return a.first.calc(x) < b.first.calc(x);
  }

  template <typename T, typename X>
  bool operator()(const std::pair<LinearFunc<T, X>, int> &a, const std::pair<T, X> &b) const
  {
    return a.first.calc(b.second) < b.first;
  }

  template <typename T, typename X>
  bool operator()(const std::pair<T, X> &a, const std::pair<LinearFunc<T, X>, int> &b) const
  {
    return a.first < b.first.calc(a.second);
  }
};

vec<f128> bisect_vec(const vec<f128> &A, const vec<f128> &B, const vec<f128> &C)
{
  auto AB = (B - A).unit();
  auto AC = (C - A).unit();
  return (AB + AC).unit();
}

std::vector<bool> calc(const std::vector<vec<f128>> &points, const std::vector<std::pair<vec<f128>, int>> &queries, const std::vector<int> &qi)
{
  auto original_convex = get_convex(points);
  { // no need to worry about vertical line
    int l = 0, r = original_convex.size();
    while (r - l >= 2 && points[original_convex[l]].x == points[original_convex[l + 1]].x) l++;
    while (r - l >= 2 && points[original_convex[r - 1]].x == points[original_convex[r - 2]].x) r--;
    original_convex = std::vector(original_convex.begin() + l, original_convex.begin() + r);
  }

  std::set<std::pair<LinearFunc<vec<f128>, f128>, int>, Compare> convex;
  std::vector<std::optional<decltype(convex)::iterator>> vecs;

  using node_t = std::pair<f128, std::pair<int, int>>;
  std::priority_queue<node_t, std::vector<node_t>, std::greater<>> pq;

  for (int i = 0; i < (int)original_convex.size(); i++) {
    vec<f128> A = points[original_convex[i]];
    auto B = 
      (i == 0) ?
      vec<f128>(A.x, A.y + 1) :
      vec<f128>(points[original_convex[i - 1]]);
    auto C = 
      (i + 1 == (int)original_convex.size()) ?
      vec<f128>(A.x, A.y + 1) :
      vec<f128>(points[original_convex[i + 1]]);

    auto A_bis = bisect_vec(A, B, C);
    f128 d = line(A, B).distance(A + A_bis);
    auto p = convex.emplace(LinearFunc(A_bis / d, A, (f128)0.0), vecs.size()).first;
    vecs.emplace_back(p);
  }

  for (int i = 0; i + 1 < (int)vecs.size(); i++) {
    auto p = vecs[i].value();
    auto q = vecs[i + 1].value();
    auto A = p->first.calc(0);
    auto B = q->first.calc(0);
    auto C = p->first.calc(1);
    auto D = q->first.calc(1);
    line AC{A, C};
    line BD{B, D};
    auto E = intersection(AC, BD);
    auto d = line(A, B).distance(E);
    pq.emplace(d, std::make_pair(p->second, q->second));
  }

  std::vector<bool> ans(queries.size());

  for (int i : qi) {
    int r = queries[i].second;

    while (!pq.empty() && pq.top().first <= r) {
      f128 t = pq.top().first;
      auto [qa, qb] = pq.top().second;
      pq.pop();
      if (!vecs[qa] || !vecs[qb]) continue;
      auto pa = vecs[qa].value();
      auto pb = vecs[qb].value();
      vecs[qa].reset();
      vecs[qb].reset();

      auto A = pa->first.calc(t);
      auto B = vec<f128>(A.x, A.y + 1);
      while (pa != convex.begin()) {
        auto qa = std::prev(pa);
        auto D = qa->first.calc(t);
        if (A.almost_same(D)) {
          vecs[qa->second].reset();
          convex.erase(qa);
        } else {
          B = D;
          break;
        }
      }
      auto C = vec<f128>(A.x, A.y + 1);
      while (std::next(pb) != convex.end()) {
        auto qb = std::next(pb);
        auto D = qb->first.calc(t);
        if (A.almost_same(D)) {
          vecs[qb->second].reset();
          convex.erase(qb);
        } else {
          C = D;
          break;
        }
      }

      auto A_bis = bisect_vec(A, B, C);
      f128 d = line(A, B).distance(A + A_bis);
      A_bis = A_bis / d;

      convex.erase(pa);
      convex.erase(pb);
      auto p = convex.emplace(LinearFunc(A_bis, A - A_bis * t, t), vecs.size()).first;
      vecs.emplace_back(p);

      if (p != convex.begin()) {
        auto q = std::prev(p);
        auto A = p->first.calc(t);
        auto B = q->first.calc(t);
        auto C = p->first.calc(t + 1);
        auto D = q->first.calc(t + 1);
        line AC{A, C};
        line BD{B, D};
        auto E = intersection(AC, BD);
        auto d = line(A, B).distance(E);
        pq.emplace(d + t, std::make_pair(q->second, p->second));
      }

      if (std::next(p) != convex.end()) {
        auto q = std::next(p);
        auto A = p->first.calc(t);
        auto B = q->first.calc(t);
        auto C = p->first.calc(t + 1);
        auto D = q->first.calc(t + 1);
        line AC{A, C};
        line BD{B, D};
        auto E = intersection(AC, BD);
        auto d = line(A, B).distance(E);
        pq.emplace(d + t, std::make_pair(p->second, q->second));
      }

    }

    auto A = queries[i].first;
    auto p = convex.lower_bound(std::make_pair(A, (f128)r));

    if (p == convex.end()) {
      if (p != convex.begin()) {
        auto B = std::prev(p)->first.calc(r);
        ans[i] = (std::fabs(B.x - A.x) <= eps && B.y - A.y <= eps);
      }
    } else if (p == convex.begin()) {
      auto B = p->first.calc(r);
      ans[i] = (std::fabs(B.x - A.x) <= eps && B.y - A.y <= eps);
    } else {
      auto B = p->first.calc(r);
      auto C = std::prev(p)->first.calc(r);
      ans[i] = (line(B, C).vec_at_x(A.x).y - A.y <= eps);
    }
  }

  return ans;
}

template <typename T = int>
T next_int()
{
  T x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -f;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}

void solve()
{
  int n = next_int();
  std::vector<vec<f128>> points(n);
  for (int i = 0; i < n; i++) {
    points[i].x = next_int();
    points[i].y = next_int();
  }
  std::sort(points.begin(), points.end());

  int m = next_int();
  std::vector<std::pair<vec<f128>, int>> queries(m);
  for (auto &[c, r] : queries) {
    c.x = next_int();
    c.y = next_int();
    r = next_int();
  }
  std::vector<int> qi(m);
  for (int i = 0; i < m; i++) qi[i] = i;
  std::sort(qi.begin(), qi.end(),
            [&queries](int x, int y)
            {
              return queries[x].second < queries[y].second;
            });

  auto ans1 = calc(points, queries, qi);
  for (auto &p : points) p.y = -p.y;
  for (auto &q : queries) q.first.y = -q.first.y;
  auto ans2 = calc(points, queries, qi);

  std::string ans;
  for (int i = 0; i < m; i++) {
    if (ans1[i] && ans2[i]) {
      ans.push_back('1');
    } else {
      ans.push_back('0');
    }
  }
  std::cout << ans << std::endl;
}

int main()
{
  int t = next_int();
  while (t--) solve();
}