POJ 3025 - Rings

http://poj.org/problem?id=3025

概要

平面上に \(n\) 個の円があり，それぞれ中心は \( (x_i, y_i) \) で半径は \(r\) である． 円と円が重なっている場合それらは同じ component を成していると考えたとき，ある component に属する円の数の最大値を答える．

制約

• \(0 \le n \le 100\)

解法

円と円の交差判定 + Union-Find．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <complex>
 4 using namespace std;
 5 typedef complex<double> P;
 6 
 7 struct circle/*{{{*/
 8 {
 9   P o;
10   double r;
11   circle() {}
12   circle(const P& p, double x) : o(p), r(x) {}
13 
14   // POJ 1418 Viva Confetti
15   // POJ 2149 Inherit the Spheres
16   inline bool intersects(const circle& c) const
17   {
18     return !contains(c) && !c.contains(*this) && abs(o - c.o) <= r + c.r;
19   }
20 
21   inline bool contains(const circle& c) const
22   {
23     return abs(o - c.o)+c.r <= r;
24   }
25 };/*}}}*/
26 
27 struct DisjointSet/*{{{*/
28 {
29   vector<int> parent;
30 
31   int root(int x)
32   {
33     if (parent[x] < 0) {
34       return x;
35     } else {
36       parent[x] = root(parent[x]);
37       return parent[x];
38     }
39   }
40 
41   explicit DisjointSet(int n) : parent(n, -1) {}
42 
43   bool unite(int x, int y)
44   {
45     const int a = root(x);
46     const int b = root(y);
47     if (a != b) {
48       if (parent[a] < parent[b]) {
49         parent[a] += parent[b];
50         parent[b] = a;
51       } else {
52         parent[b] += parent[a];
53         parent[a] = b;
54       }
55       return true;
56     } else {
57       return false;
58     }
59   }
60 
61   int size(int x) { return -parent[root(x)]; }
62 };/*}}}*/
63 
64 int main()
65 {
66   int N;
67   while (scanf("%d", &N) != EOF && N != -1) {
68     vector<circle> cs;
69     DisjointSet s(N);
70     for (int i = 0; i < N; i++) {
71       double x, y, r;
72       scanf("%lf %lf %lf", &x, &y, &r);
73       circle c(P(x, y), r);
74       for (int j = 0; j < i; j++) {
75         if (cs[j].contains(c) || cs[j].intersects(c)) {
76           s.unite(i, j);
77         }
78       }
79       cs.push_back(c);
80     }
81     int ans = 1;
82     for (int i = 0; i < N; i++) {
83       ans = max(ans, s.size(i));
84     }
85     printf("The largest component contains %d rings\n", ans);
86   }
87   return 0;
88 }