植树
题目描述
小明和朋友们一起去郊外植树，他们带了一些在实验室中精心研究出的小树苗。
一共有 n 个人，每个人挑选了一个适合植树的位置，一共 n 个位置。每人准备在自己的位置种下一棵树苗。
但他们遇到一个问题：有的树苗比较大，而有的位置太近，如果同时种下会“撞到一起”。
我们将每棵树视为一个圆，圆心是植树的位置，半径为树的半径。如果两棵树的圆相交（相切不算），那么这两棵树不能同时种下，称为发生冲突。
他们决定只选择其中一部分树苗种下去，要求：
- 没有任意两棵树发生冲突；
- 所有种下树的面积总和最大。
输入描述
- 第一行一个整数
n（1 ≤ n ≤ 30），表示准备植树的位置数。 - 接下来
n行，每行三个整数x y r，表示树苗的种植位置坐标 (x,y) 和树的半径r。
其中：
- 0 ≤ x, y ≤ 1000
- 1 ≤ r ≤ 1000
输出描述
输出一个整数，表示在不冲突的情况下，可以植树的总面积除以 π 的值。
因为每棵树的面积为 π * r²，所以答案是总面积除以 π 后的整数。
输入示例
6
1 1 2
1 4 2
1 7 2
4 1 2
4 4 2
4 7 2
输出示例
12
c++代码
#include<bits/stdc++.h>
using namespace std;
struct cir{
int x, y, r;
};
int n, ans = 0;
vector<cir> cirs, mid;
void dfs(int index, int tem) {
if (index == cirs.size()) {
ans = max(ans, tem);
return;
}
bool key = true;
for (int i = 0; i < mid.size() && key; i++) {
if ((mid[i].x - cirs[index].x) * (mid[i].x - cirs[index].x) + (mid[i].y - cirs[index].y) * (mid[i].y - cirs[index].y) < (mid[i].r + cirs[index].r) * (mid[i].r + cirs[index].r)) key = false;
}
dfs(index + 1, tem);
if (key) mid.push_back(cirs[index]), dfs(index + 1, tem + cirs[index].r * cirs[index].r), mid.pop_back();
}
int main() {
cin >> n;
cirs = vector<cir>(n);
for (int i = 0; i < n; i++) cin >> cirs[i].x >> cirs[i].y >> cirs[i].r;
dfs(0, 0);
cout << ans;
return 0;
}//by wqs
题目解析
dfs+剪枝，如果已经选择的有和当前节点冲突，则不能选