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.
The first line of input contains one integer n (1 ≤ n ≤ 3), denoting the number of circles.
The following n lines each contains three space-separated integers x, y and r ( - 10 ≤ x, y ≤ 10, 1 ≤ r ≤ 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.
3
0 0 1
2 0 1
4 0 1
4
3
0 0 2
3 0 2
6 0 2
6
3
0 0 2
2 0 2
1 1 2
8
For the first example,
For the second example,
For the third example,
思路一：每次新添加一个圆时，求出与前面所有的圆产生的交点，有多少交点，就新增加多少区域。但有两种情况要特判，无交点时，区域数要加1；前两个圆相离或内含且第三个圆与前两个圆都有交点时，区域数要减1。
废话：你问我为什么区域数就是这个，我也是对数据画图得出的规律啊...之后学习了一下欧拉公式后：f = e - v + c + 1。f是区域数，c是连通块个数。其实这个规律就是欧拉公式啊...
另我是手推的圆交公式，该找一套板子了...
代码一（自己推交点的搓代码）：
#include <iostream> #include <fstream> #include <sstream> #include <cstdlib> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <set> #include <map> #include <list> #include <iomanip> #include <cctype> #include <cassert> #include <bitset> #include <ctime> using namespace std; #define pau system("pause") #define ll long long #define pii pair<int, int> #define pb push_back #define mp make_pair #define clr(a, x) memset(a, x, sizeof(a)) #define pdd pair<double, double> const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; const double EPS = 1e-9; struct circle { ll x, y, r; } c[3]; ll n; vector<pdd> vec; bool equ(pdd p1, pdd p2) { double x1 = p1.first, y1 = p1.second; double x2 = p2.first, y2 = p2.second; return fabs(x1 - x2) < EPS && fabs(y1 - y2) < EPS; } ll pow2(ll x) {return x * x;} bool in(circle c1, circle c2) { int x1 = c1.x, y1 = c1.y, r1 = c1.r; int x2 = c2.x, y2 = c2.y, r2 = c2.r; int d1 = pow2(r1 - r2); int d2 = pow2(x1 - x2) + pow2(y1 - y2); return d1 > d2; } bool out(circle c1, circle c2) { int x1 = c1.x, y1 = c1.y, r1 = c1.r; int x2 = c2.x, y2 = c2.y, r2 = c2.r; int d1 = pow2(r1 + r2); int d2 = pow2(x1 - x2) + pow2(y1 - y2); return d1 < d2; } bool Insec(circle c1, circle c2) { ll x1 = c1.x, y1 = c1.y, r1 = c1.r; ll x2 = c2.x, y2 = c2.y, r2 = c2.r; if (x1 == x2 && y1 == y2) return false; const ll con = pow2(x2) + pow2(y2) + pow2(r1) - pow2(x1) - pow2(y1) - pow2(r2); if (x1 == x2) { ll a = 4 * (pow2(y2 - y1) + pow2(x2 - x1)); ll b = 4 * (x1 - x2) * (con - 2 * (y2 - y1) * y1) - 8 * x1 * pow2(y2 - y1); ll c = 4 * pow2(y2 - y1) * pow2(x1) + pow2(con - 2 * (y2 - y1) * y1) - pow2(r1) * 4 * pow2(y2 - y1); ll det = b * b - 4 * a * c; //printf("%lld %lld %lld %lld ", con, a, b, c); if (det < 0) { return false; } else if (!det) { double _x1 = 1.0 * (-b) / (2 * a); double _y1 = (2 * (x1 - x2) * _x1 + con) / (2 * (y2 - y1)); vec.pb(mp(_x1, _y1)); } else { double sqr_det = sqrt(det); double _x1 = 1.0 * (-b + sqr_det) / (2 * a); double _x2 = 1.0 * (-b - sqr_det) / (2 * a); double _y1 = (2 * (x1 - x2) * _x1 + con) / (2 * (y2 - y1)); double _y2 = (2 * (x1 - x2) * _x2 + con) / (2 * (y2 - y1)); vec.pb(mp(_x1, _y1)); vec.pb(mp(_x2, _y2)); } } else { ll a = 4 * (pow2(x2 - x1) + pow2(y2 - y1)); ll b = 4 * (y1 - y2) * (con - 2 * (x2 - x1) * x1) - 8 * y1 * pow2(x2 - x1); ll c = 4 * pow2(x2 - x1) * pow2(y1) + pow2(con - 2 * (x2 - x1) * x1) - pow2(r1) * 4 * pow2(x2 - x1); ll det = b * b - 4 * a * c; if (det < 0) { return false; } else if (!det) { double _y1 = 1.0 * (-b) / (2 * a); double _x1 = (2 * (y1 - y2) * _y1 + con) / (2 * (x2 - x1)); vec.pb(mp(_x1, _y1)); } else { double sqr_det = sqrt(det); double _y1 = 1.0 * (-b + sqr_det) / (2 * a); double _y2 = 1.0 * (-b - sqr_det) / (2 * a); double _x1 = (2 * (y1 - y2) * _y1 + con) / (2 * (x2 - x1)); double _x2 = (2 * (y1 - y2) * _y2 + con) / (2 * (x2 - x1)); vec.pb(mp(_x1, _y1)); vec.pb(mp(_x2, _y2)); } } return true; } int main() { scanf("%d", &n); for (ll i = 0; i < n; ++i) { scanf("%lld%lld%lld", &c[i].x, &c[i].y, &c[i].r); } ll ans = 2; for (ll i = 1; i < n; ++i) { vec.clear(); int flag = 1; for (ll j = 0; j < i; ++j) { if (!Insec(c[i], c[j])) { flag = 0; } } sort(vec.begin(), vec.end()); ll tt = vec.size(); for (ll j = 0; j < (ll)vec.size() - 1; ++j) { if (equ(vec[j], vec[j + 1])) --tt; } if (i == 2 && (in(c[0], c[1]) || out(c[0], c[1])) && flag) --tt; ans += max(tt, 1ll); /*for (ll j = 0; j < vec.size(); ++j) { printf("%.3f %.3f ", vec[j].first, vec[j].second); }*/ } printf("%d", ans); return 0; }