小明看著煙火,耀眼的圓形在天空中綻放,譜出一張美麗動人的霓虹光舞。紅色、黃色、綠色、藍色,絢爛的光輝在黑夜中是如此動人。
活動結束後小明看著他拍攝的照片,不幸的是這些煙火都糊掉變成一個一個圓了。他好奇在一張相片中天空被煙火分成幾塊區域?一塊區域被定義成平面上一塊面積非零的連通部份,而且邊界都由圓的邊界組成且區域不能包含任何圓的邊界。
以下是小明所撰寫的程式,不過當中出了一點小錯誤,你可以在 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';
}
輸入的第一行有一個整數 $n\ (1 \leq n \leq 3)$ 代表圓形的數量。
接下來有 $n$ 行,每行有空白分開的三個整數 $x, y, r\ (-10 \leq x, y \leq 10, 1 \leq r \leq 10)$,代表這個圓的中心在平面上的 $(x, y)$ 且半徑為 $r$。
任兩個圓皆相異。
輸出區域的數量。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~2 | 範例測資。 | 0 |
2 | 0~133 | 無額外限制。 | 50 |