codeforces D. An overnight dance in discotheque

The crowdedness of the discotheque would never stop our friends from having fun, but a bit more spaciousness won’t hurt, will it?

The discotheque can be seen as an infinite xy-plane, in which there are a total of n dancers. Once someone starts moving around, they will move only inside their own movement range, which is a circular area Ci described by a center (xi, yi) and a radius ri. No two ranges’ borders have more than one common point, that is for every pair (i, j) (1 ≤ i < j ≤ n) either ranges Ci and Cj are disjoint, or one of them is a subset of the other. Note that it’s possible that two ranges’ borders share a single common point, but no two dancers have exactly the same ranges.

Tsukihi, being one of them, defines the spaciousness to be the area covered by an odd number of movement ranges of dancers who are moving. An example is shown below, with shaded regions representing the spaciousness if everyone moves at the same time.

But no one keeps moving for the whole night after all, so the whole night’s time is divided into two halves — before midnight and after midnight. Every dancer moves around in one half, while sitting down with friends in the other. The spaciousness of two halves are calculated separately and their sum should, of course, be as large as possible. The following figure shows an optimal solution to the example above.

By different plans of who dances in the first half and who does in the other, different sums of spaciousness over two halves are achieved. You are to find the largest achievable value of this sum.

Input
The first line of input contains a positive integer n (1 ≤ n ≤ 1 000) — the number of dancers.

The following n lines each describes a dancer: the i-th line among them contains three space-separated integers xi, yi and ri ( - 106 ≤ xi, yi ≤ 106, 1 ≤ ri ≤ 106), describing a circular movement range centered at (xi, yi) with radius ri.

Output
Output one decimal number — the largest achievable sum of spaciousness over two halves of the night.

The output is considered correct if it has a relative or absolute error of at most 10 - 9. Formally, let your answer be a, and the jury’s answer be b. Your answer is considered correct if .

Examples
input
5
2 1 6
0 4 1
2 -1 3
1 -2 1
4 -1 1
output
138.23007676
input
8
0 0 1
0 0 2
0 0 3
0 0 4
0 0 5
0 0 6
0 0 7
0 0 8
output
289.02652413

题意：

给定一群人，他们喜欢在迪厅里面跳舞，每一个人都有自己跳舞的范围，都是圆
组成的。半径和圆心都给出，但是有个条件是每一个只能在晚上的上半夜或者
是下半夜跳舞，并且两个人跳舞范围有冲突的话不能一起跳，不过有个信息是跳
舞的人可能完全覆盖别人或者是不覆盖，不会出现只覆盖部分的情况。
求出所有跳舞可能之中面积所能覆盖的最大值。

思路：

一开始我以为纯纯的数学题，后来发现不是，好伤！完全被题目长度所吓到了！
不该！
思路比较神奇，需要推出来！
根据每一个人被覆盖的情况可以大致分为三种：

1. 没有别人覆盖过
2. 被覆盖的次数为奇数次
3. 被覆盖的次数为偶数次

当你算到这里的时候其实结果已经出来了，第一种直接加入答案之中，那么被覆
盖的次数为偶数的话是上半夜和下班都不能跳舞的人，奇数次是可以在上半夜
或者下半夜跳舞的人。

#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>using namespace std;#define pi acos(-1)
const int maxn = 1005;struct Cir
{double x,y,r;int cnt;
}cir[maxn];int n;int cmp(Cir a,Cir b)
{if(a.r == b.r) return a.x == b.x ? b.y > a.y : a.x < b.x;elsereturn a.r > b.r;
}int judge(int i,int j)
{return (cir[i].x-cir[j].x)*(cir[i].x-cir[j].x)+(cir[i].y-cir[j].y)*(cir[i].y-cir[j].y) < (cir[i].r+cir[j].r)*(cir[i].r+cir[j].r);
}int main()
{//freopen("in.txt","r",stdin);scanf("%d",&n);for(int i = 1;i <= n; i++) {scanf("%lf%lf%lf",&cir[i].x,&cir[i].y,&cir[i].r);cir[i].cnt = 0;}sort(cir+1,cir+n+1,cmp);for(int i = 1;i <= n; i++) {for(int j = i + 1;j <= n; j++) {if(judge(i,j))cir[j].cnt++;}}double ans = 0;for(int i = 1;i <= n; i++) {if(cir[i].cnt == 0)ans += cir[i].r*cir[i].r*pi;else if(cir[i].cnt%2)ans += cir[i].r*cir[i].r*pi;elseans -= cir[i].r*cir[i].r*pi;}printf("%.7f\n",ans);return 0;
}