codeforces 814 D. An overnight dance in discotheque （贪心+bfs）

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

题意：给出奇数个舞者，每个舞者都有中心坐标和行动半径，而且这些点组成的园要么相互包含要么没有交集求，讲这些点分成两部分最大面积是多少。

面积计算方法详见题目，很好理解有图示。

 

题解：这题挺简单的就考虑一下包含与不包含的就行了。具体看一下代码挺好理解的，主要是题目给出的这些点组成的园要么相互包含要么没有交集求导致

这题变得很简单

#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#define PI acos(-1)
using namespace std;
const int M = 1e3 + 10;
typedef long long ll;
vector<int>vc[M];//存该点包含的点
ll x[M] , y[M] , r[M];
ll PP(ll x) {return x * x;}
ll lowbi[M];//值为0表示该点没被包括，值不为零表示该点被其他点罩着
ll n;
ll lev[M];//下标的奇偶来判断是加还是减其实只要出现奇数次就可以加或者0的时候，由于一开始为0是不可能被包含的所以不用想加上就行。
void bfs() {
queue<int>q;
for(int i = 0 ; i < n ; i++) {
if(!lowbi[i]) q.push(i);
}
memset(lev , 0 , sizeof(lev));
while(!q.empty()) {
int v = q.front();
q.pop();
int len = vc[v].size();
for(int i = 0 ; i < len ; i++) {
int u = vc[v][i];
lev[u] = lev[v] + 1;
lowbi[u]--;
if(!lowbi[u]) q.push(u);
}
}
}
int main() {
cin >> n;
for(int i = 0 ; i < n ; i++) cin >> x[i] >> y[i] >> r[i];
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < n ; j++) {
if(i == j) continue;
if(r[i] > r[j] && r[i] * r[i] >= PP(x[i] - x[j]) + PP(y[i] - y[j])) {
vc[i].push_back(j);
lowbi[j]++;
}
}
}
ll ans = 0;
bfs();
for(int i = 0 ; i < n ; i++) {
if(lev[i] == 0 || lev[i] % 2) cout << i << endl , ans += r[i] * r[i];
else ans -= r[i] * r[i];
}
printf("%.12lfn" , ans * PI);
return 0;
}