fork download
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <complex>
  4. #include <vector>
  5. #include <utility>
  6. #include <algorithm>
  7. #include <cassert>
  8. #include <queue>
  9. using namespace std;
  10.  
  11. #define rep(i, n) for (int i = 0; i < (int)(n); i++)
  12.  
  13. const double EPS = 1e-10;
  14. typedef complex<double> p_t;
  15.  
  16. double dot(const p_t &p, const p_t &q) { return real(conj(p) * q); }
  17. double det(const p_t &p, const p_t &q) { return imag(conj(p) * q); }
  18.  
  19. double dist_l_p(const p_t &p, const p_t &a, const p_t &u) {
  20. return abs(det(p - a, u)) / abs(u);
  21. }
  22.  
  23. pair<double, double> cross_l_c(p_t a, const p_t &u, const p_t &c, double r) {
  24. a -= c;
  25. double b = real(u * conj(a)), d = b * b - norm(u) * (norm(a) - r * r);
  26. d = max(d, 0.0);
  27. return make_pair((-b + sqrt(d)) / norm(u), (-b - sqrt(d)) / norm(u));
  28. }
  29.  
  30. pair<p_t, p_t> cross_c_c(const p_t &c, double r, const p_t &d, double s) {
  31. double di = abs(c - d);
  32. double l = ((r * r - s * s) / di + di) / 2.0, n = sqrt(r * r - l * l);
  33. p_t e = c + (d - c) * l / di, p = (d - c) * n / di * p_t(0.0, -1.0);
  34. return make_pair(e + p, e - p);
  35. }
  36.  
  37. int N, M;
  38. p_t C[110];
  39. double R[110];
  40.  
  41. int V;
  42. vector<pair<double, int>> vs[110][2];
  43.  
  44. vector<vector<int> > adj;
  45.  
  46. bool solve(p_t P, p_t Q) {
  47. P += p_t(0.0001, 0.0001);
  48. Q += p_t(0.0001, 0.0001);
  49.  
  50. rep (i, N) {
  51. bool p = abs(P - C[i]) < R[i];
  52. bool q = abs(Q - C[i]) < R[i];
  53. if (p != q) return false;
  54. }
  55.  
  56. V = 0;
  57. rep (i, N) {
  58. vs[i][0].clear();
  59. vs[i][1].clear();
  60. }
  61.  
  62. rep (i, N) rep (j, i) {
  63. double d = abs(C[i] - C[j]);
  64. if (d > R[i] + R[j] || d < fabs(R[i] - R[j])) continue;
  65.  
  66. pair<p_t, p_t> xs = cross_c_c(C[i], R[i], C[j], R[j]);
  67. rep (k, 2) {
  68. p_t x = (k == 0 ? xs.first : xs.second);
  69. int v0 = V;
  70. V += 4;
  71.  
  72. { // From |i|
  73. double th = arg(x - C[i]);
  74. vs[i][1].push_back(make_pair(th, v0 + 0));
  75. vs[i][1].push_back(make_pair(th, v0 + 1));
  76. vs[i][0].push_back(make_pair(th, v0 + 2));
  77. vs[i][0].push_back(make_pair(th, v0 + 3));
  78. }
  79. { // From |j|
  80. double th = arg(x - C[j]);
  81. vs[j][1].push_back(make_pair(th, v0 + 1));
  82. vs[j][1].push_back(make_pair(th, v0 + 3));
  83. vs[j][0].push_back(make_pair(th, v0 + 0));
  84. vs[j][0].push_back(make_pair(th, v0 + 2));
  85. }
  86. }
  87. }
  88.  
  89. int V2 = V;
  90. vector<pair<double, int> > s2v;
  91. rep (i, N) {
  92. double d = dist_l_p(C[i], P, Q - P);
  93. if (d > R[i] - EPS) continue;
  94. pair<double, double> ss = cross_l_c(P, Q - P, C[i], R[i]);
  95. if (ss.first > ss.second) swap(ss.first, ss.second);
  96.  
  97. rep (k, 2) {
  98. double s = (k == 0 ? ss.first : ss.second);
  99. if (s < 0 || 1 < s) continue;
  100. int v0 = V;
  101. V += 2;
  102.  
  103. p_t x = P + s * (Q - P);
  104. double th = arg(x - C[i]);
  105. vs[i][(k == 0 ? 1 : 0)].push_back(make_pair(th, v0 + 0));
  106. vs[i][(k == 0 ? 0 : 1)].push_back(make_pair(th, v0 + 1));
  107. s2v.push_back(make_pair(s, v0 + 0));
  108. s2v.push_back(make_pair(s, v0 + 1));
  109. }
  110. }
  111. int vp = V++;
  112. int vq = V++;
  113. s2v.push_back(make_pair(0, vp));
  114. s2v.push_back(make_pair(1, vq));
  115. adj.clear();
  116. adj.resize(V);
  117. rep (i, N) {
  118. rep (k, 2) {
  119. sort(vs[i][k].begin(), vs[i][k].end());
  120. rep (j, vs[i][k].size()) {
  121. int v = vs[i][k][j].second;
  122. int w = vs[i][k][(j + 1) % vs[i][k].size()].second;
  123. if (v < V2 && v / 4 == w / 4) continue;
  124. adj[v].push_back(w);
  125. adj[w].push_back(v);
  126. }
  127. }
  128. }
  129.  
  130. sort(s2v.begin(), s2v.end());
  131. assert(s2v.size() % 2 == 0);
  132. for (int i = 0; i < (int)s2v.size(); i += 2) {
  133. int v = s2v[i].second;
  134. int w = s2v[i + 1].second;
  135. adj[v].push_back(w);
  136. adj[w].push_back(v);
  137. }
  138.  
  139. queue<int> que;
  140. vector<bool> vis(V);
  141. que.push(vp);
  142. vis[vp] = true;
  143. while (!que.empty()) {
  144. int v = que.front();
  145. que.pop();
  146. if (v == vq) return true;
  147.  
  148. for (int w : adj[v]) {
  149. if (vis[w]) continue;
  150. vis[w] = true;
  151. que.push(w);
  152. }
  153. }
  154.  
  155. return false;
  156. }
  157.  
  158. int main() {
  159. for (;;) {
  160. scanf("%d%d", &N, &M);
  161. if (N == 0 && M == 0) return 0;
  162.  
  163. rep (i, N) {
  164. double x, y;
  165. scanf("%lf%lf%lf", &x, &y, &R[i]);
  166. C[i] = p_t(x, y);
  167. }
  168.  
  169. rep (i, M) {
  170. double x1, y1, x2, y2;
  171. scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
  172. printf("%s%c",
  173. solve(p_t(x1, y1), p_t(x2, y2)) ? "YES" : "NO",
  174. i == M - 1 ? '\n' : ' ');
  175. }
  176. }
  177. }
  178.  
Success #stdin #stdout 0s 3448KB
stdin
5 3
0 0 1000
1399 1331 931
0 1331 500
1398 0 400
2000 360 340
450 950 1600 380
450 950 1399 1331
450 950 450 2000
1 2
50 50 50
0 10 100 90
0 10 50 50
2 2
50 50 50
100 50 50
40 50 110 50
40 50 0 0
4 1
25 100 26
75 100 26
50 40 40
50 160 40
50 81 50 119
6 1
100 50 40
0 50 40
50 0 48
50 50 3
55 55 4
55 105 48
50 55 55 50
20 6
270 180 50
360 170 50
0 0 50
10 0 10
0 90 50
0 180 50
90 180 50
180 180 50
205 90 50
180 0 50
65 0 20
75 30 16
90 78 36
105 30 16
115 0 20
128 48 15
128 100 15
280 0 30
330 0 30
305 65 42
0 20 10 20
0 20 10 0
50 30 133 0
50 30 133 30
90 40 305 20
90 40 240 30
16 2
0 0 50
0 90 50
0 180 50
90 180 50
180 180 50
205 90 50
180 0 50
65 0 20
115 0 20
90 0 15
280 0 30
330 0 30
305 65 42
75 40 16
90 88 36
105 40 16
128 35 250 30
90 50 305 20
0 0
stdout
YES NO NO
YES NO
NO NO
NO
YES
YES NO NO YES NO NO
NO NO