[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]:\n", i);
        rep(j, 1, cc[i]) printf("(%.5lf, %.5lf)\n", 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\n", E, V, C);
    printf("%d\n", E - V + C + 1); // */

    return 0;
}