蓝桥杯 19. 植树

植树

题目描述

小明和朋友们一起去郊外植树，他们带了一些在实验室中精心研究出的小树苗。

一共有 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+剪枝，如果已经选择的有和当前节点冲突，则不能选