MT2084 检测敌人

思路：

1. 以装置为中心->以敌人为中心。

以敌人为中心，r为半径做圆，与x轴交于a,b点，则在[a,b]之间的装置都能覆盖此敌人。

每个敌人都有[a,b]区间，则此题转化为：有多少个装置能覆盖到这些[a,b]区间。（“覆盖”指的是装置所在的位置在[a,b]线段上）

2.使用贪心：首先将所有线段进行排序（按右端点由小到大），每次将装置放在第一个未覆盖线段的右端点上。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
struct enemy
{double x, y, r, l;bool v;
} e[N];
bool cmp(enemy a, enemy b)
{return a.r < b.r;
}
int main()
{int n;double r;while (cin >> n >> r && !(n == 0 && r == 0)){bool flag = false;memset(e, 0, sizeof e);for (int i = 1; i <= n; i++){cin >> e[i].x >> e[i].y;if (r * r < e[i].y * e[i].y) // 不可覆盖{flag = true;}else{ // 求在x轴上的投影e[i].l = e[i].x - sqrt(r * r - e[i].y * e[i].y);e[i].r = sqrt(r * r - e[i].y * e[i].y) + e[i].x;e[i].v = false;}}if (flag){ // 以敌人为中心，r为半径的圆与x无交点：不可覆盖cout << -1 << endl;continue;}sort(e + 1, e + 1 + n, cmp);int ans = 0;for (int i = 1; i <= n; i++){ // 从小到大检测每一条线段if (e[i].v == false){ // 此敌人还未被检测for (int j = i; j <= n; j++){if (e[j].v == false && e[j].l <= e[i].r) // 未被检测的敌人线段与当前线段有交集{e[j].v = true;}}e[i].v = true;ans++;}}cout << ans << endl;}return 0;
}