TopCoder

Anemois
四小時內刻出gomory的我

User's AC Ratio

100.0% (26/26)

Submission's AC Ratio

36.8% (39/106)

Tags

Description

小明看著煙火,耀眼的圓形在天空中綻放,譜出一張美麗動人的霓虹光舞。紅色、黃色、綠色、藍色,絢爛的光輝在黑夜中是如此動人。

活動結束後小明看著他拍攝的照片,不幸的是這些煙火都糊掉變成一個一個圓了。他好奇在一張相片中天空被煙火分成幾塊區域?一塊區域被定義成平面上一塊面積非零的連通部份,而且邊界都由圓的邊界組成且區域不能包含任何圓的邊界。

以下是小明所撰寫的程式,不過當中出了一點小錯誤,你可以在 edit distance 5000 以內幫他修正成正確的程式嗎?

#include <bits/stdc++.h>
#define point complex<double>
#define e exp(-20)
// eps = e^ -20 ~= 2e-9
using namespace std;


// circle with radius r intersects line ax + by + c = 0
vector<point> circIntersectLine(double x, double y, double r, double a, double b, double c) {
    double f = (a * x + b * y + c), n = a * a + b * b;
    point p(x - f / n * a, y - f / n * b);
    double d = r * r - f * f / n;
    if (abs(d) < 1e-9)
        return {p};
    else if (d < 0)
        return {};
    else {
        double t = sqrt(d / n);
        return {p - point(-b, a) * t, p + point(-b, a) * t};
    }
}

vector<point> circIntersectCirc(double x0, double y0, double r0, double x1, double y1, double r1) {
    return circIntersectLine(x0, y0, r0, 2 * (x1 - x0), 2 * (y1 - y0), x0 * x0 - x1 * x1 + y0 * y0 - y1 * y1 - r0 * r0 + r1 * r1);
}

pair<double, double> convert(point p) {
    return make_pair(p.real(), p.imag());
}

int n, x[3], y[3], r[3];
vector<point> v;

signed main() {
    cin >> n;
    int cc = n;
    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i] >> r[i];

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            auto u = circIntersectCirc(x[i], y[i], r[i], x[j], y[j], r[j]);
            if (!u.empty())
                cc = max(1, cc - 1);
            for (auto p : u)
                v.emplace_back(p);
        }

    sort(v.begin(), v.end(), [](auto p, auto q){
        return convert(p) < convert(q);});

    v.resize(unique(v.begin(), v.end(), [](auto p, auto q)
                    { return norm(p - q) < 1e-9; }) -
             v.begin());

    int E = 0;
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (auto p : v)
            if (abs(norm(p - point(x[i], y[i])) - r[i] * r[i]) < 1e-9)
                cnt++;

        E += cnt;
    }
    // V - E + F = cc + 1
    cout << cc - v.size() + E + 1 << '\n';
}

Input Format

輸入的第一行有一個整數 $n\ (1 \leq n \leq 3)$ 代表圓形的數量。

接下來有 $n$ 行,每行有空白分開的三個整數 $x, y, r\ (-10 \leq x, y \leq 10, 1 \leq r \leq 10)$,代表這個圓的中心在平面上的 $(x, y)$ 且半徑為 $r$。

任兩個圓皆相異。

Output Format

輸出區域的數量。

Sample Input 1

3
0 0 1
2 0 1
4 0 1

Sample Output 1

4

Sample Input 2

3
0 0 2
3 0 2
6 0 2

Sample Output 2

6

Sample Input 3

3
0 0 2
2 0 2
1 1 2

Sample Output 3

8

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資。 0
2 0~133 無額外限制。 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 100 262144 65536 1 2
1 100 262144 65536 1 2
2 100 262144 65536 1 2
3 100 262144 65536 2
4 100 262144 65536 2
5 100 262144 65536 2
6 100 262144 65536 2
7 100 262144 65536 2
8 100 262144 65536 2
9 100 262144 65536 2
10 100 262144 65536 2
11 100 262144 65536 2
12 100 262144 65536 2
13 100 262144 65536 2
14 100 262144 65536 2
15 100 262144 65536 2
16 100 262144 65536 2
17 100 262144 65536 2
18 100 262144 65536 2
19 100 262144 65536 2
20 100 262144 65536 2
21 100 262144 65536 2
22 100 262144 65536 2
23 100 262144 65536 2
24 100 262144 65536 2
25 100 262144 65536 2
26 100 262144 65536 2
27 100 262144 65536 2
28 100 262144 65536 2
29 100 262144 65536 2
30 100 262144 65536 2
31 100 262144 65536 2
32 100 262144 65536 2
33 100 262144 65536 2
34 100 262144 65536 2
35 100 262144 65536 2
36 100 262144 65536 2
37 100 262144 65536 2
38 100 262144 65536 2
39 100 262144 65536 2
40 100 262144 65536 2
41 100 262144 65536 2
42 100 262144 65536 2
43 100 262144 65536 2
44 100 262144 65536 2
45 100 262144 65536 2
46 100 262144 65536 2
47 100 262144 65536 2
48 100 262144 65536 2
49 100 262144 65536 2
50 100 262144 65536 2
51 100 262144 65536 2
52 100 262144 65536 2
53 100 262144 65536 2
54 100 262144 65536 2
55 100 262144 65536 2
56 100 262144 65536 2
57 100 262144 65536 2
58 100 262144 65536 2
59 100 262144 65536 2
60 100 262144 65536 2
61 100 262144 65536 2
62 100 262144 65536 2
63 100 262144 65536 2
64 100 262144 65536 2
65 100 262144 65536 2
66 100 262144 65536 2
67 100 262144 65536 2
68 100 262144 65536 2
69 100 262144 65536 2
70 100 262144 65536 2
71 100 262144 65536 2
72 100 262144 65536 2
73 100 262144 65536 2
74 100 262144 65536 2
75 100 262144 65536 2
76 100 262144 65536 2
77 100 262144 65536 2
78 100 262144 65536 2
79 100 262144 65536 2
80 100 262144 65536 2
81 100 262144 65536 2
82 100 262144 65536 2
83 100 262144 65536 2
84 100 262144 65536 2
85 100 262144 65536 2
86 100 262144 65536 2
87 100 262144 65536 2
88 100 262144 65536 2
89 100 262144 65536 2
90 100 262144 65536 2
91 100 262144 65536 2
92 100 262144 65536 2
93 100 262144 65536 2
94 100 262144 65536 2
95 100 262144 65536 2
96 100 262144 65536 2
97 100 262144 65536 2
98 100 262144 65536 2
99 100 262144 65536 2
100 100 262144 65536 2
101 100 262144 65536 2
102 100 262144 65536 2
103 100 262144 65536 2
104 100 262144 65536 2
105 100 262144 65536 2
106 100 262144 65536 2
107 100 262144 65536 2
108 100 262144 65536 2
109 100 262144 65536 2
110 100 262144 65536 2
111 100 262144 65536 2
112 100 262144 65536 2
113 100 262144 65536 2
114 100 262144 65536 2
115 100 262144 65536 2
116 100 262144 65536 2
117 100 262144 65536 2
118 100 262144 65536 2
119 100 262144 65536 2
120 100 262144 65536 2
121 100 262144 65536 2
122 100 262144 65536 2
123 100 262144 65536 2
124 100 262144 65536 2
125 100 262144 65536 2
126 100 262144 65536 2
127 100 262144 65536 2
128 100 262144 65536 2
129 100 262144 65536 2
130 100 262144 65536 2
131 100 262144 65536 2
132 100 262144 65536 2
133 100 262144 65536 2