codeforces 814D （DFS）

题目链接：http://codeforces.com/contest/814/problem/D

题意：n个人跳舞，跳舞范围为半径为R的圆，任意两个圆只有至多一个交点。现在把这n个人分成前半夜和后半夜跳舞，被覆盖奇数次的数值-S，偶数次的+S，求数值最大值

思路：因为任意两个圆至多只有1个交点，所以可以建立成若干棵树（森林），每棵树半径最大的为根，每个节点的父节点为能覆盖它的最小圆，如样例1为

　　　　　　　　　　　　　　　　　　　　　　　　　　1

　　　　　　　　　　　　　　　　　　　　　　　　　/　　

  　　　　　　　　　　　　　　　　　　　　　　　 2         3

　　　　　　　　　　　　　　　　　　　　　　　　　　　/　  

　　　　　　　　　　　　　　　　　　　　　　　　　　 4       5

每棵树都要被拆成两部分，设深度为i的面积为S(i)，由于包含关系知S(1)>S(2)>S(3)>......，S(1)必为正，ans = S(1) + S(2) - S(3) + S(4) - S(5) + ......

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5;
const double eps = 1e-10;
const double pi = acos(-1);
bool vis[N];
int n;
double ans = 0;
int sgn(double x,double y)
{
if(fabs(x - y) < eps)
return 0;
return x > y ? 1 : -1;
}
struct Circle
{
double x,y,r;
bool operator < (Circle t)
{
return r > t.r;
}
}circle[N];
bool covered(Circle a,Circle b)
{
if(sgn(a.r + b.r, sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y))) <= 0)
return 0;
return 1;
}
void dfs(int i,int depth)
{
if(vis[i])
return;
vis[i] = 1;
if(depth == 1 || depth % 2 == 0)
ans += circle[i].r * circle[i].r * pi;
else
ans -= circle[i].r * circle[i].r * pi;
for(int j = i + 1; j <= n; j++)
{
if(covered(circle[i],circle[j]))
dfs(j,depth + 1);
}
}
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%lf %lf %lf",&circle[i].x,&circle[i].y,&circle[i].r);
sort(circle + 1, circle + n + 1);
for(int i = 1; i <= n; i++)
dfs(i,1);
printf("%.8lfn",ans);
return 0;
}