AOJ 1198: Don't Cross the Circles!/円を横切るな！

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1198&lang=ja

解法

$P, Q$ のうち一方のみが含まれる円が 1 つ以上存在する場合、 $P$ と $Q$ をその円と交差しないように結ぶことはできないので、答えは明らかに NO となります。

$P, Q$ がともに 1 個以上の円に含まれていて、 $P$ を含む円の集合と $Q$ を含む円の集合が一致する場合、3 つ以上の円に共通部分はなく 2 つの円が接することはないという条件から、答えは必ず YES となります。

よって、 $P, Q$ がともにどの円にも含まれていない場合のみ考えればよいです。

$n$ 個の円の中心を考え、円 $i, j$ が二点で交わるとき、またそのときのみに、円 $i$ の中心とと円 $j$ の中心を線分で結ぶと、2 つの線分は端点以外では共有点を持たず、点 $P, Q$ をどの円とも交差しないように結べることとどの線分とも交差しないように結べることは同値になります。

$n$ 個の円の中心を頂点、中心を結ぶ線分を辺とした平面グラフ $G$ を考えると、 $G$ の辺は平面を何個かの領域に分割し、点 $P, Q$ をどの辺とも交差しないように結べることは点 $P, Q$ が同じ領域に属することと同値になります。 $G$ が木である場合は領域が 1 つしかないので答えは必ず YES になります。そうでない場合は、 $G$ には閉路が必ず存在します。閉路に現れる頂点を順に列挙し、それぞれの頂点に対応する円の中心を順に線分で結んだ多角形を考えます。もし点 $P, Q$ のうち一方のみがこの多角形に含まれている場合、多角形の辺と交差せずに点 $P, Q$ を結ぶことはできないので、答えは NO となります。そうでない場合、閉路の辺を一つ取りその辺を取り除き $G’$ とすると、辺が平面を分割している領域のうちその辺を境に隣接している二つ ( $A, B$ とします) が併合され新しい領域ができます。ここで、点 $P, Q$ がそれぞれ領域 $A, B$ または $B, A$ に属していることはありえないので、点 $P, Q$ が同じ領域に属することは、グラフ $G’$ の辺が平面を分割する領域について点 $P, Q$ が同じ領域に属することと同値になります。よって、点 $P, Q$ のうち一方のみが多角形の内部にあることで答えが NO であることが確定するかグラフ $G$ が木になり答えが YES が確定するまで $G$ から閉路を取り辺を取り除くことを繰り返すことで、点 $P, Q$ をどの円とも交差しないように結べるかどうか判定することができます。

時間計算量は $O(n ^ 2 m)$ です。

実装

judge.u-aizu.ac.jp

#include <bits/stdc++.h>
using namespace std;
const double EPS = 0.0001;
struct point{
  double x, y;
  point(){
  }
  point(double x, double y): x(x), y(y){
  }
  point operator -(point P){
    return point(x - P.x, y - P.y);
  }
};
double abs(point P){
  return sqrt(P.x * P.x + P.y * P.y);
}
double dist(point P, point Q){
  return abs(Q - P);
}
double cross(point P, point Q){
  return P.x * Q.y - P.y * Q.x;
}
struct line{
  point A, B;
  line(point A, point B): A(A), B(B){
  }
};
point vec(line L){
  return L.B - L.A;
}
bool segment_intersect(line L1, line L2){
  if (cross(L1.A - L2.A, vec(L2)) * cross(L1.B - L2.A, vec(L2)) > 0){
    return false;
  }
  if (cross(L2.A - L1.A, vec(L1)) * cross(L2.B - L1.A, vec(L1)) > 0){
    return false;
  }
  return true;
}
bool point_in_polygon(point P, vector<point> Q){
  int N = Q.size();
  point P2 = point(P.x + 100000, P.y + 123456);
  int cnt = 0;
  for (int i = 0; i < N; i++){
    line L1(Q[i], Q[(i + 1) % N]);
    line L2(P, P2);
    if (segment_intersect(L1, L2)){
      cnt++;
    }
  }
  if (cnt % 2 == 1){
    return true;
  } else {
    return false;
  }
}
struct circle{
  point C;
  double r;
  circle(){
  }
};
bool point_in_circle(point P, circle C){
  return dist(P, C.C) < C.r;
}
bool circle_intersects(circle C1, circle C2){
  double d = dist(C1.C, C2.C);
  return abs(C1.r - C2.r) - EPS < d && d < C1.r + C2.r + EPS;
}
void dfs(vector<vector<int>> &E, vector<int> &r, vector<int> &p, vector<int> &d, int r2, int v){
  r[v] = r2;
  for (int w : E[v]){
    if (r[w] == -1){
      d[w] = d[v] + 1;
      p[w] = v;
      dfs(E, r, p, d, r2, w);
    }
  }
}
vector<int> detect_cycle(vector<vector<int>> E){
  int N = E.size();
  vector<int> r(N, -1);
  vector<int> p(N, -1);
  vector<int> d(N, 0);
  for (int i = 0; i < N; i++){
    if (p[i] == -1){
      dfs(E, r, p, d, i, i);
    }
  }
  for (int i = 0; i < N; i++){
    for (int j : E[i]){
      if (r[i] == r[j] && d[j] - d[i] > 1){
        vector<int> c;
        for (int v = j; v != i; v = p[v]){
          c.push_back(v);
        }
        c.push_back(i);
        return c;
      }
    }
  }
  return vector<int>();
}
int main(){
  while (true){
    int n, m;
    cin >> n >> m;
    if (n == 0 && m == 0){
      break;
    }
    vector<circle> C(n);
    for (int i = 0; i < n; i++){
      cin >> C[i].C.x >> C[i].C.y >> C[i].r;
    }
    for (int i = 0; i < m; i++){
      point P, Q;
      cin >> P.x >> P.y >> Q.x >> Q.y;
      set<int> st1, st2;
      for (int j = 0; j < n; j++){
        if (point_in_circle(P, C[j])){
          st1.insert(j);
        }
        if (point_in_circle(Q, C[j])){
          st2.insert(j);
        }
      }
      if (!st1.empty() || !st2.empty()){
        if (st1 == st2){
          cout << "YES";
        } else {
          cout << "NO";
        }
      } else {
        vector<vector<int>> E(n);
        for (int j = 0; j < n; j++){
          for (int k = j + 1; k < n; k++){
            if (circle_intersects(C[j], C[k])){
              E[j].push_back(k);
              E[k].push_back(j);
            }
          }
        }
        bool ok = true;
        while (true){
          vector<int> c = detect_cycle(E);
          if (c.empty()){
            break;
          }
          int cnt = c.size();
          vector<point> p(cnt);
          for (int j = 0; j < cnt; j++){
            p[j] = C[c[j]].C;
          }
          if (point_in_polygon(P, p) != point_in_polygon(Q, p)){
            ok = false;
          }
          for (int j = 0; j < E[c[0]].size(); j++){
            if (E[c[0]][j] == c[1]){
              E[c[0]].erase(E[c[0]].begin() + j);
              break;
            }
          }
          for (int j = 0; j < E[c[1]].size(); j++){
            if (E[c[1]][j] == c[0]){
              E[c[1]].erase(E[c[1]].begin() + j);
              break;
            }
          }
        }
        if (ok){
          cout << "YES";
        } else {
          cout << "NO";
        }
      }
      if (i < m - 1){
        cout << ' ';
      }
    }
    cout << endl;
  }
}