codeforces 814D An overnight dance in discotheque

正解：贪心。

首先我们可以计算出每个圆被多少个圆覆盖。

很显然，最外面的圆是肯定要加上的。

然后第二层的圆也是要加上的。那么第三层就不可能被加上了。同理，第四层的圆又一定会被加上。

然后我们可以发现一个贪心策略，没被覆盖和被覆盖奇数次的圆加上，被覆盖偶数次的圆减去。

可以发现这样的贪心策略是最优的。

 1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 #define N (1005)
 6 
 7 using namespace std;
 8 
 9 const double pi=acos(-1.0);
10 
11 double x[N],y[N],r[N],ans;
12 int cov[N],n;
13 
14 il int gi(){
15   RG int x=0,q=1; RG char ch=getchar();
16   while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
17   if (ch=='-') q=-1,ch=getchar();
18   while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
19   return q*x;
20 }
21 
22 il double dis(RG int i,RG int j){
23   return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
24 }
25 
26 il int check(RG int i,RG int j){
27   return r[i]<r[j] && dis(i,j)<=r[j]-r[i];
28 }
29 
30 int main(){
31 #ifndef ONLINE_JUDGE
32   freopen("dance.in","r",stdin);
33   freopen("dance.out","w",stdout);
34 #endif
35   n=gi();
36   for (RG int i=1;i<=n;++i) x[i]=gi(),y[i]=gi(),r[i]=gi();
37   for (RG int i=1;i<=n;++i)
38     for (RG int j=1;j<=n;++j){
39       if (i==j) continue; cov[i]+=check(i,j);
40     }
41   for (RG int i=1;i<=n;++i)
42     if (!cov[i]) ans+=pi*r[i]*r[i];
43     else if (cov[i]&1) ans+=pi*r[i]*r[i];
44     else ans-=pi*r[i]*r[i];
45   printf("%0.8lf
",ans); return 0;
46 }