#1072232 (C++23) No.2602 Real Collider

提出ソース
結果

問題	No.2602 Real Collider
ユーザー	kusaf_
提出日時	2025-04-16 09:16:27
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	WA
実行時間	-
コード長	15,870 bytes
コンパイル時間	4,529 ms
コンパイル使用メモリ	311,360 KB
実行使用メモリ	7,848 KB
最終ジャッジ日時	2025-04-16 09:16:41
合計ジャッジ時間	12,551 ms
ジャッジサーバーID （参考情報）	judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 72 WA * 6
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;





using Real = double;
constexpr Real EPS = 1e-10, PI = 3.141592653589793238462643383279L;
bool eq(Real a, Real b = 0) { return fabs(b - a) < EPS; }
int sign(Real a) { return !eq(a) ? a > 0 ? 1 : -1 : 0; }
Real rtod(Real r) { return r * 180.0 / PI; }
Real dtor(Real d) { return d * PI / 180.0; }

struct Point {
  Real x, y;
  Point(): x(0), y(0) {}
  Point(Real x, Real y): x(x), y(y) {}
  template<typename T, typename U> Point(const pair<T, U> &p): x(p.first), y(p.second) {}
  Point operator+(const Point &p) const { return {x + p.x, y + p.y}; }
  Point operator-(const Point &p) const { return {x - p.x, y - p.y}; }
  Point operator*(Real r) const { return {x * r, y * r}; }
  Point operator/(Real r) const { return {x / r, y / r}; }
  Point &operator+=(const Point &p) { return (*this) = (*this) + p; }
  Point &operator-=(const Point &p) { return (*this) = (*this) - p; }
  Point &operator*=(Real r) { return (*this) = (*this) * r; }
  Point &operator/=(Real r) { return (*this) = (*this) / r; }
  bool operator<(const Point &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const Point &p) const { return x == p.x && y == p.y; }
  bool operator!=(const Point &p) const { return !((*this) == p); }
  Point rotate(Real t) const { return {x * cos(t) - y * sin(t), x * sin(t) + y * cos(t)}; }
  Real real() const { return x; }
  Real imag() const { return y; }
  friend Real real(const Point &p) { return p.x; }
  friend Real imag(const Point &p) { return p.y; }
  friend Real dot(const Point &l, const Point &r) { return l.x * r.x + l.y * r.y; }
  friend Real cross(const Point &l, const Point &r) { return l.x * r.y - l.y * r.x; }
  friend Real abs(const Point &p) { return sqrt(p.x * p.x + p.y * p.y); }
  friend Real norm(const Point &p) { return p.x * p.x + p.y * p.y; }
  friend Real distance(const Point &l, const Point &r) { return abs(l - r); }
  friend Real arg(const Point &p) { return atan2(p.y, p.x); }
  friend istream &operator>>(istream &is, Point &p) {
    Real a, b;
    is >> a >> b;
    p = Point{a, b};
    return is;
  }
  friend ostream &operator<<(ostream &os, const Point &p) { return os << p.x << " " << p.y; }
};
using Points = vector<Point>;

Real angle(const Point &a, const Point &b, const Point &c) {  // ∠ABC (acute)
  const Point x = a - b, y = c - b;
  Real t1 = arg(x), t2 = arg(y);
  if(t1 > t2) { swap(t1, t2); }
  Real t = t2 - t1;
  return min(t, 2 * PI - t);
}

int ccw(const Point &a, const Point &b, const Point &c) {
  const Point x = b - a, y = c - a;
  if(cross(x, y) > EPS) { return +1; }  // a,b,c counterclockwise
  if(cross(x, y) < -EPS) { return -1; }  // a,b,c clockwise
  if(min(norm(x), norm(y)) < EPS * EPS) { return 0; }  // c=a or c=b
  if(dot(x, y) < EPS) { return +2; }  // c-a-b
  if(norm(x) < norm(y)) { return -2; }  // a-b-c
  return 0;  // a-c-b
}

using Polygon = vector<Point>;
using Polygons = vector<Polygon>;

int Contains(const Polygon &P, const Point &p) {  // 0:out, 1:on, 2:in
  bool in = false;
  const int N = P.size();
  for(int i = 0; i < N; i++) {
    Point a = P[i] - p, b = P[(i + 1) % N] - p;
    if(a.y > b.y) { swap(a, b); }
    if(a.y < EPS && b.y > EPS && cross(a, b) < -EPS) { in = !in; }
    if(eq(cross(a, b)) && dot(a, b) < EPS) { return 1; }
  }
  return in ? 2 : 0;
}

int ConvexContains(const Polygon &C, const Point &p) {  // 0:out, 1:on, 2:in
  const int N = C.size();
  if(N == 0) { return 0; }
  if(N == 1) { return C[0] == p; }
  Real b1 = cross(C[1] - C[0], p - C[0]), b2 = cross(C[N - 1] - C[0], p - C[0]);
  if(b1 < -EPS || b2 > EPS) { return 0; }
  int L = 1, R = N - 1;
  while(R - L > 1) {
    int M = (L + R) >> 1;
    (cross(p - C[0], C[M] - C[0]) >= 0 ? R : L) = M;
  }
  Real v = cross(C[L] - p, C[R] - p);
  if(eq(v)) { return 1; }
  else if(v > 0) { return eq(b1) || eq(b2) ? 1 : 2; }
  else { return 0; }
}

bool isConvex(const Polygon &P) {
  const int N = P.size();
  for(int i = 0; i < N; i++) {
    if(ccw(P[(i + N - 1) % N], P[i], P[(i + 1) % N]) == -1) { return false; }
  }
  return true;
}

template<bool boundary = false> Polygon ConvexHull(Polygon P, bool sorted = false) {
  if(!sorted) {
    sort(P.begin(), P.end());
    P.erase(unique(P.begin(), P.end()), P.end());
  }
  const int N = P.size();
  int k = 0;
  if(N <= 2) { return P; }
  Polygon C(2 * N);
  Real e = boundary ? -EPS : EPS;
  for(int i = 0; i < N; C[k++] = P[i++]) {
    while(k >= 2 && cross(C[k - 1] - C[k - 2], P[i] - C[k - 1]) < e) { k--; }
  }
  for(int i = N - 2, t = k + 1; i >= 0; C[k++] = P[i--]) {
    while(k >= t && cross(C[k - 1] - C[k - 2], P[i] - C[k - 1]) < e) { k--; }
  }
  C.resize(k - 1);
  return C;
}

Real Area(const Polygon &P) {
  const int N = P.size();
  Real A = 0;
  for(int i = 0; i < N; i++) { A += cross(P[i], P[(i + 1) % N]); }
  return A * 0.5;
}

pair<int, int> ConvexDiameter(const Polygon &P) {
  const int N = P.size();
  int i = 0, j = 0;
  for(int k = 1; k < N; k++) {
    if(P[k].y < P[i].y) { i = k; }
    if(P[k].y > P[j].y) { j = k; }
  }
  ll maxdis = norm(P[i] - P[j]);
  int maxi = i, maxj = j, is = i, js = j;
  do {
    if(cross(P[(i + 1) % N] - P[i], P[(j + 1) % N] - P[j]) >= 0) { j = (j + 1) % N; }
    else { i = (i + 1) % N; }
    if(norm(P[i] - P[j]) > maxdis) {
      maxdis = norm(P[i] - P[j]);
      maxi = i, maxj = j;
    }
  } while(i != is || j != js);
  return minmax(maxi, maxj);
}

pair<Point, Point> ClosestPair(Points P) {
  const int N = P.size();
  assert(N >= 2);
  sort(P.begin(), P.end());
  Real d = 9e18;
  Point a, b;
  auto f = [&](auto &&f, int l, int r) -> void {
    const int m = (l + r) >> 1;
    if(r - l <= 1) { return; }
    const Real x = P[m].x;
    f(f, l, m);
    f(f, m, r);
    inplace_merge(P.begin() + l, P.begin() + m, P.begin() + r, [](const auto &a, const auto &b) { return a.y < b.y; });
    vector<int> B;
    for(int i = l; i < r; i++) {
      if(sign(abs(P[i].x - x) - d) > 0) { continue; }
      for(int j = (int)B.size() - 1; j >= 0; j--) {
        if(sign(P[i].y - P[B[j]].y - d) > 0) { break; }
        if(sign(d - distance(P[i], P[B[j]])) > 0) {
          d = distance(P[i], P[B[j]]);
          a = P[i], b = P[B[j]];
        }
      }
      B.emplace_back(i);
    }
  };
  f(f, 0, N);
  return {a, b};
}

struct Line {
  Point a, b;
  Line() = default;
  Line(const Point &a, const Point &b): a(a), b(b) {}
  Line(const Real &A, const Real &B, const Real &C) {  // Ax + By = C
    if(eq(A)) {
      assert(!eq(B));
      a = Point(0, C / B), b = Point(1, C / B);
    }
    else if(eq(B)) { a = Point(C / A, 0), b = Point(C / A, 1); }
    else if(eq(C)) { a = Point(0, C / B), b = Point(1, (C - A) / B); }
    else { a = Point(0, C / B), b = Point(C / A, 0); }
  }
  friend istream &operator>>(istream &is, Line &l) { return is >> l.a >> l.b; }
  friend ostream &operator<<(ostream &os, const Line &l) { return os << l.a << " to " << l.b; }
};
using Lines = vector<Line>;

bool parallel(const Line &l, const Line &r) { return eq(cross(l.b - l.a, r.b - r.a)); }
bool orthogonal(const Line &l, const Line &r) { return eq(dot(l.a - l.b, r.a - r.b)); }
Point projection(const Line &l, const Point &p) { return l.a + (l.a - l.b) * (dot(p - l.a, l.a - l.b) / norm(l.a - l.b)); }
Point reflection(const Line &l, const Point &p) { return projection(l, p) * 2 - p; }
bool intersect(const Line &l, const Point &p) { return abs(ccw(l.a, l.b, p)) != 1; }
int intersect(const Line &l, const Line &r) { return parallel(l, r) ? intersect(l, r.a) ? 2 : 0 : 1; }  // 0:parallel, 1:intersect 2:l=r
Real distance(const Line &l, const Point &p) { return distance(p, projection(l, p)); }
Real distance(const Line &l, const Line &r) { return intersect(l, r) ? 0 : distance(l, r.a); }
Point crosspoint(const Line &l, const Line &r) {
  Real A = cross(l.b - l.a, r.b - r.a), B = cross(l.b - l.a, l.b - r.a);
  return eq(A) && eq(B) ? r.a : r.a + (r.b - r.a) * B / A;
}
Line PerpendicularBisector(const Point &l, const Point &r) {
  Point m = (l + r) * 0.5, d = r - l;
  Point p(m.x - d.y, m.y + d.x);
  return Line(m, p);
}
Point Circumcenter(const Point &a, const Point &b, const Point &c) { return crosspoint(PerpendicularBisector(a, b), PerpendicularBisector(a, c)); }

Polygon ConvexCut(const Polygon &P, const Line &l) {
  const int N = P.size();
  Polygon r;
  for(int i = 0; i < N; i++) {
    const Point &now = P[i], &nxt = P[(i + 1) % N];
    Real cf = cross(l.a - now, l.b - now), cs = cross(l.a - nxt, l.b - nxt);
    if(sign(cf) >= 0) { r.emplace_back(now); }
    if(sign(cf) * sign(cs) < 0) { r.emplace_back(crosspoint(Line(now, nxt), l)); }
  }
  return r;
}

struct Segment : Line {
  Segment() = default;
  using Line::Line;
};
using Segments = vector<Segment>;

bool intersect(const Segment &s, const Point &p) { return ccw(s.a, s.b, p) == 0; }
bool intersect(const Line &l, const Segment &s) { return sign(cross(l.b - l.a, s.a - l.a)) * sign(cross(l.b - l.a, s.b - l.a)) <= 0; }
bool intersect(const Segment &l, const Segment &r) { return ccw(l.a, l.b, r.a) * ccw(l.a, l.b, r.b) <= 0 && ccw(r.a, r.b, l.a) * ccw(r.a, r.b, l.b) <= 0; }
Real distance(const Segment &s, const Point &p) { return intersect(s, projection(s, p)) ? distance(p, projection(s, p)) : min(distance(s.a, p), distance(s.b, p)); }
Real distance(const Line &l, const Segment &s) { return intersect(l, s) ? 0 : min(distance(l, s.a), distance(l, s.b)); }
Real distance(const Segment &l, const Segment &r) { return intersect(l, r) ? 0 : min({distance(l, r.a), distance(l, r.b), distance(r, l.a), distance(r, l.b)}); }

void MergeSegments(Segments &S) {
  auto merge_if_able = [](Segment &s1, const Segment &s2) {
    if(sign(cross(s1.b - s1.a, s2.b - s2.a)) == 1) { return 0; }
    if(ccw(s1.a, s2.a, s1.b) == 1 || ccw(s1.a, s2.a, s1.b) == -1) { return 0; }
    if(ccw(s1.a, s1.b, s2.a) == -2 || ccw(s2.a, s2.b, s1.a) == -2) { return 0; }
    s1 = Segment(min(s1.a, s2.a), max(s1.b, s2.b));
    return 1;
  };
  for(int i = 0; i < (int)S.size(); i++) {
    if(S[i].b < S[i].a) { swap(S[i].a, S[i].b); }
  }
  for(int i = 0; i < (int)S.size(); i++) {
    for(int j = i + 1; j < (int)S.size(); j++) {
      if(merge_if_able(S[i], S[j])) {
        S[j--] = S.back();
        S.pop_back();
      }
    }
  }
}

vector<vector<int>> SegmentArrangement(Segments &S, Points &P) {
  vector<vector<int>> g;
  const int N = S.size();
  for(int i = 0; i < N; i++) {
    P.push_back(S[i].a);
    P.push_back(S[i].b);
    for(int j = i + 1; j < N; j++) {
      const Point p1 = S[i].b - S[i].a, p2 = S[j].b - S[j].a;
      if(eq(cross(p1, p2))) { continue; }
      if(intersect(S[i], S[j])) { P.push_back(crosspoint(S[i], S[j])); }
    }
  }
  sort(P.begin(), P.end());
  P.erase(unique(P.begin(), P.end()), P.end());
  const int M = P.size();
  g.resize(M);
  for(int i = 0; i < N; i++) {
    vector<int> v;
    for(int j = 0; j < M; j++) {
      if(intersect(S[i], P[j])) { v.push_back(j); }
    }
    for(int j = 1; j < (int)v.size(); j++) {
      g[v[j - 1]].push_back(v[j]);
      g[v[j]].push_back(v[j - 1]);
    }
  }
  return g;
}

struct Circle {
  Point p;
  Real r{};
  Circle() = default;
  Circle(const Point &p, const Real &r): p(p), r(r) {}
  friend istream &operator>>(istream &is, Circle &c) { return is >> c.p >> c.r; }
  friend ostream &operator<<(ostream &os, Circle &c) { return os << c.p << " ," << c.r; }
};
using Circles = vector<Circle>;

int contains(const Circle &c, const Point &p) { return sign(c.r - distance(c.p, p)) + 1; }  // 0:out, 1:on, 2:in
bool intersect(const Circle &c, const Point &p) { return eq(c.r, distance(c.p, p)); }
int intersect(const Circle &c, const Line &l) { return contains(c, projection(l, c.p)); }
int intersect(const Circle &c, const Segment &s) {
  int r = intersect(c, Line(s)), f = ccw(s.a, s.b, projection(s, c.p));
  if(r == 0) { return 0; }
  if(r == 1) { return f == 0 ? 1 : 0; }
  int f1 = sign(abs(c.p - s.a) - c.r), f2 = sign(abs(c.p - s.b) - c.r);
  if(f1 < 0 && f2 < 0) { return 0; }
  if(f1 < 0 || f2 < 0) { return 1; }
  if(f1 == 0 && f2 == 0) { return 2; }
  if(f1 == 0 || f2 == 0) { return f == 0 ? 2 : 1; }
  return f == 0 ? 2 : 0;
}
int intersect(const Circle &a, const Circle &b) {  // +2:外部 -2:内部 +1:外接 -1:内接 0:2点で交わる
  Real d = distance(a.p, b.p), R = a.r + b.r, r = fabs(a.r - b.r);
  if(sign(d - R) > 0) { return +2; }
  if(sign(d - r) < 0) { return -2; }
  if(eq(d, R)) { return +1; }
  if(eq(d, r)) { return -1; }
  return 0;
}
Points crosspoint(const Circle &c, const Line &l) {
  Point h = projection(l, c.p);
  if(intersect(c, l) == 0) { return {}; }
  if(intersect(c, l) == 1) { return {h}; }
  Point e = (l.b - l.a) / distance(l.a, l.b) * sqrt(norm(c.r) - norm(h - c.p));
  return {h + e, h - e};
}
Points crosspoint(const Circle &c, const Segment &s) {
  if(intersect(c, s) == 0) { return {}; }
  Points r = crosspoint(c, Line(s));
  if(intersect(c, s) == 2) { return r; }
  if(dot(s.a - r[0], s.b - r[0]) > 0) { swap(r[0], r[1]); }
  return {r[0]};
}
Points crosspoint(const Circle &l, const Circle &r) {
  const int i = intersect(l, r);
  if(abs(i) == 2) { return {}; }
  Real d = distance(l.p, r.p), t = acos((l.r * l.r - r.r * r.r + d * d) / (2 * l.r * d)), s = arg(r.p - l.p);
  Point e(l.r, 0), p = l.p + e.rotate(s + t), q = l.p + e.rotate(s - t);
  if(abs(i) == 1) { return {p}; }
  return {p, q};
}
Points tangent(const Circle &c, const Point &p) {
  const int i = contains(c, p);
  if(i == 2) { return {}; }
  if(i == 1) { return {p}; }
  return crosspoint(c, Circle(p, sqrt(norm(p - c.p) - c.r * c.r)));
}
Lines tangent(Circle &l, Circle &r) {
  Lines ret;
  if(sign(l.r - r.r) < 0) { swap(l, r); }
  Real g = norm(l.p - r.p);
  if(eq(g)) { return ret; }
  Point u = (r.p - l.p) / sqrt(g), v = u.rotate(PI * 0.5);
  for(int s : {-1, 1}) {
    Real h = (l.r + s * r.r) / sqrt(g);
    if(eq(1 - h * h)) { ret.emplace_back(Line(l.p + u * l.r, l.p + (u + v) * l.r)); }
    else if(sign(1 - h * h) > 0) {
      Point uu = u * h, vv = v * sqrt(1 - h * h);
      ret.emplace_back(Line(l.p + (uu + vv) * l.r, r.p - (uu + vv) * r.r * s));
      ret.emplace_back(Line(l.p + (uu - vv) * l.r, r.p - (uu - vv) * r.r * s));
    }
  }
  return ret;
}

Real Area(const Circle &c, const Polygon &P) {
  auto calc = [&](auto &&calc, const Point &a, const Point &b) -> Real {
    auto va = c.p - a, vb = c.p - b;
    Real f = cross(va, vb), ret = 0;
    if(eq(f)) { return ret; }
    if(max(abs(va), abs(vb)) < c.r + EPS) { return f; }
    if(distance(Segment(a, b), c.p) > c.r - EPS) {
      Point t(va.x * vb.x + va.y * vb.y, va.x * vb.y - va.y * vb.x);
      return norm(c.r) * arg(t);
    }
    auto u = crosspoint(c, Segment(a, b));
    if((int)u.size() == 1) { u.emplace_back(u[0]); }
    vector<Point> tot = {a, u[0], u[1], b};
    for(int i = 0; i < 3; i++) { ret += calc(calc, tot[i], tot[i + 1]); }
    return ret;
  };
  const int N = P.size();
  if(N < 3) { return 0; }
  Real A = 0;
  for(int i = 0; i < N; i++) { A += calc(calc, P[i], P[(i + 1) % N]); }
  return A * 0.5;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll Q;
  cin >> Q;

  Point X, Y, Z;
  cin >> X >> Y >> Z;

  vector<Point> O = {Point(), (X + Y) / 2, (Y + Z) / 2, (Z + X) / 2};
  vector<Circle> C = {Circle(Point(), 1e10), Circle(O[1], distance(Y, O[1])), Circle(O[2], distance(Z, O[2])), Circle(O[3], distance(X, O[3]))};

  if(abs(ccw(X, Y, Z)) == 1) {
    O[0] = Circumcenter(X, Y, Z);
    C[0] = Circle(O[0], distance(X, O[0]));
  }

  Real r = C[0].r;
  ll idx = 0;
  for(ll i = 1; i < 4; i++) {
    if(i == 1 && !contains(C[i], Z)) { continue; }
    if(i == 2 && !contains(C[i], X)) { continue; }
    if(i == 3 && !contains(C[i], Y)) { continue; }
    if(r > C[i].r) {
      idx = i;
      r = C[i].r;
    }
  }

  while(Q--) {
    Point P;
    cin >> P;
    cout << (contains(C[idx], P) ? "Yes" : "No") << "\n";
  }
}
yukicoder

結果

ソースコード
