# 题解 CF814D 【An overnight dance in discotheque】

#define MAXN 3050

using namespace std ;
const double Pi = acos(-1.0) ;
struct C{
double x, y, r ;
}base[MAXN] ;
double Ans ;
int i, j, k ;
long long dp[MAXN][2][2] ;
int N, mark[MAXN], fa[MAXN] ;

inline double dist(C A, C B){
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)) ;
}
inline double get_S(C A){ return Pi * A.r * A.r ; }
inline bool check_in(C A, C B){ return A.r + B.r > dist(A, B) ; }
namespace DP{
#define to(k) E[k].to
struct Edge{
int next, to ;
}E[MAXN << 1] ;
inline void Add(int u, int v){
}
void do_dp(int u, int faa){
long long f[2][2] ; memset(f, 0, sizeof(f)) ;
for (int k = head[u] ; k ; k = E[k].next){
if (to(k) == faa) continue ;
do_dp(to(k), u) ;
for (int ii = 0 ; ii <= 1 ; ++ ii)
for (int jj = 0 ; jj <= 1 ; ++ jj)
f[ii][jj] += dp[to(k)][ii][jj] ;
}
for (int ii = 0 ; ii <= 1 ; ++ ii)
for (int jj = 0 ; jj <= 1 ; ++ jj)
dp[u][ii][jj] = max(f[ii ^ 1][jj] + (1ll * (ii ? -1 : 1) * base[u].r * base[u].r),
f[ii][jj ^ 1] + (1ll * (jj ? -1 : 1) * base[u].r * base[u].r)) ;
}
inline bool Comp(C A, C B){
return A.r > B.r ; }
void solve1(){
sort(base + 1, base + N + 1, Comp) ;
for (i = 1 ; i <= N ; ++ i)
for(j = i + 1 ; j <= N ; ++ j)
if (check_in(base[i], base[j]))
if (!fa[j] || base[fa[j]].r > base[i].r) fa[j] = i ;
for (i = 1 ; i <= N ; ++ i) if (fa[i]) Add(i, fa[i]) ;
for (i = 1 ; i <= N ; ++ i) if (!fa[i]) do_dp(i, 0), Ans += dp[i][0][0] ;
printf("%.8lf", Ans * Pi) ;
}
}
namespace Greedy{
inline bool Comp(C A, C B){ return A.r > B.r ; }
void solve2(){
sort(base + 1, base + N + 1, Comp) ;
for (i = 1 ; i <= N ; ++ i)
for(j = i + 1 ; j <= N ; ++ j)
if (check_in(base[i], base[j])) ++ mark[j] ;
for (i = 1 ; i <= N ; ++ i)
if (!mark[i] || (mark[i] & 1)) Ans += get_S(base[i]) ; else Ans -= get_S(base[i]) ;
printf("%.8lf", Ans) ;
}
}
int main(){
cin >> N ;
for (i = 1 ; i <= N ; ++ i)
scanf("%lf%lf%lf", &base[i].x, &base[i].y, &base[i].r) ;
if (N >= 500) DP :: solve1() ; else Greedy :: solve2() ; return 0 ;
}

2019-03-16 19:02:16 in 题解