[codeforces934E]A Colourful Prospect
试题描述
Firecrackers scare Nian the monster, but they're wayyyyy too noisy! Maybe fireworks make a nice complement.
Little Tommy is watching a firework show. As circular shapes spread across the sky, a splendid view unfolds on the night of Lunar New Year's eve.
A wonder strikes Tommy. How many regions are formed by the circles on the sky? We consider the sky as a flat plane. A region is a connected part of the plane with positive area, whose bound consists of parts of bounds of the circles and is a curve or several curves without self-intersections, and that does not contain any curve other than its boundaries. Note that exactly one of the regions extends infinitely.
求 (n) 个圆将平面划分成的区域个数。
输入
The first line of input contains one integer (n) ((1 le n le 3)), denoting the number of circles.
The following (n) lines each contains three space-separated integers (x), (y) and (r) (( - 10 le x, y le 10, 1 le r le 10)), describing a circle whose center is ((x, y)) and the radius is (r). No two circles have the same (x), (y) and (r) at the same time.
输出
Print a single integer — the number of regions on the plane.
输入示例1
3
0 0 1
2 0 1
4 0 1
输出示例1
4
输入示例2
3
0 0 2
3 0 2
6 0 2
输出示例2
6
输入示例3
3
0 0 2
2 0 2
1 1 2
输出示例3
8
数据规模及约定
见“输入”
题解
这题要用到平面上的欧拉公式：(V - E + R = C + 1)，其中 (V)(vertex) 表示交点数目，(E)(edge) 表示边数，(R)(region) 表示区域数，(C)(connection) 用来分割的线所构成的连通块个数。（英文是我自己 YY 的）
然后这题就好做了，(V) 非常好求，两两圆求一下交点去重即可；(E) 就是每个圆上的交点个数之和（注意如果一个圆不与任何圆相交，那么它不能算作一条边）；(C) 也可以用并查集啥的统计一下；于是我们就算出 (R) 了。
分类讨论的话可能这辈子做不完这道题了。而且 (n) 可以出到 (1000) 级别
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define rep(i, s, t) for(int i = (s), mi = (t); i <= mi; i++)
#define dwn(i, s, t) for(int i = (s), mi = (t); i >= mi; i--)
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
const double eps = 1e-9;
struct Vector {
double x, y;
Vector() {}
Vector(double _, double __): x(_), y(__) {}
Vector operator - (const Vector& t) const { return Vector(x - t.x, y - t.y); }
double len() { return sqrt(x * x + y * y); }
bool operator < (const Vector& t) const { return abs(x - t.x) > eps ? x < t.x : y < t.y; }
bool operator == (const Vector& t) const { return abs(x - t.x) <= eps && abs(y - t.y) <= eps; }
} ps[100], crs[5][100];
int cp, cc[5];
struct Circle {
Vector p; double r;
Circle() {}
Circle(Vector _, double __): p(_), r(__) {}
Vector point(double a) { return Vector(cos(a) * r + p.x, sin(a) * r + p.y); }
} cs[5];
double angle(Vector x) { return atan2(x.y, x.x); }
vector <Vector> getcross(Circle c1, Circle c2) {
vector <Vector> p; p.resize(0);
Vector t = c2.p - c1.p;
double d = t.len(), a = angle(t);
if(abs(d) <= eps) return p;
if(d < abs(c2.r - c1.r) || d > c2.r + c1.r) return p;
double da = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d));
Vector p1 = c1.point(a + da), p2 = c1.point(a - da);
p.push_back(p1);
if(p1 == p2) return p;
p.push_back(p2);
return p;
}
int fa[5];
int findset(int x) { return x == fa[x] ? x : fa[x] = findset(fa[x]); }
int main() {
int n = read();
rep(i, 1, n) {
int x = read(), y = read(), r = read();
cs[i] = Circle(Vector(x, y), r);
fa[i] = i;
}
int V, E = 0, C = n;
rep(i, 1, n) {
rep(j, 1, n) if(i != j) {
vector <Vector> tmp = getcross(cs[i], cs[j]);
for(auto k : tmp) crs[i][++cc[i]] = k;
if(tmp.size() > 0) {
int u = findset(i), v = findset(j);
if(u != v) fa[v] = u, C--;
}
}
sort(crs[i] + 1, crs[i] + cc[i] + 1);
cc[i] = unique(crs[i] + 1, crs[i] + cc[i] + 1) - crs[i] - 1;
E += cc[i];
/*printf("cs[%d]:
", i);
rep(j, 1, cc[i]) printf("(%.5lf, %.5lf)
", crs[i][j].x, crs[i][j].y); // */
rep(j, 1, cc[i]) ps[++cp] = crs[i][j];
}
sort(ps + 1, ps + cp + 1);
cp = unique(ps + 1, ps + cp + 1) - ps - 1;
V = cp;
// printf("E: %d, V: %d, C: %d
", E, V, C);
printf("%d
", E - V + C + 1); // */
return 0;
}