P1158 导弹拦截

[永遠の記憶 ~ Precious Memories]施工D8

转载自luogu

2020.3.15

P1158 导弹拦截

Noip2010 T3

题目传送门

这是一道关于排序的题，好像非常有名的样子
很多人都跟我提到过

一看到觉得很简单，
就是两个定点，求一个最小的距离ans
使得以这两个定点为圆心，以ans为半径的圆囊括所有的点。

然后按照这个思路写了出来，刚准备初见切，
结果只有40分
先附上代码:

#include <bits/stdc++.h>
using namespace std;

typedef long double ll;


ll x1, yy1, x2, y2;
ll n;
ll xax, yay;
ll ans1, ans2;
ll ans = 0;

ll dist(ll x1, ll yy1, ll x2, ll y2) {
	return sqrt((x1 - x2) * (x1 - x2) + (yy1 - y2) * (yy1 - y2));
}

int main() {
	cin >> x1 >> yy1 >> x2 >> y2;
	cin >> n;
	for (ll i = 1; i <= n; ++i) {
		cin >> xax >> yay;
		ll t1 = dist(x1, yy1, xax, yay);
		ll t2 = dist(x2, y2, xax, yay);
		if (t1 == min(t1, t2)) {
			ans1 = max(ans1, t1);
		}
		else {
			ans2 = max(ans2, t2);
		}
	}
	ans = ans1 * ans1 + ans2 * ans2;
	cout << ans << endl;
	return 0;
}

很容易观察出来，上面的代码思路有问题
上面的代码是一个朴素的枚举，
取所有点中离第一个导弹最近的，然后算出这个点离第二个导弹的距离 这个思路是错的

我们换种思路，考虑到题目的算法是排序
所以我们就用一个结构体数组来存下现在这个点分别到第一个导弹和第二个导弹的距离
并且预处理这个距离
然后对这个结构体数组进行排序，以到第一个点的距离作为关键字，这个过程的时间复杂度是O(nlogn)

然后我们再去枚举每个点到A点和B点的距离的最小值，这个过程的时间复杂度是O(n)
综合起来，我们可以写出最后的代码 代码如下:

#include <bits/stdc++.h>
using namespace std;

typedef int ll;

ll const maxn = 1e5 + 5;
ll x1, yy1, x2, y2;
ll n;
ll ans1;
ll ans = 0;
ll xx, yy;

ll dist(ll xx1, ll yyy1, ll xx2, ll yy2) {
	return (xx1 - xx2) * (xx1 - xx2) + (yyy1 - yy2) * (yyy1 - yy2);
} // 开根会有误差  

struct node {
	ll d1, d2;
} p[maxn];

bool cmp(const node &n1, const node &n2) {
	return n1.d1 < n2.d1;
}

int main() {
	scanf("%d%d%d%d", &x1, &yy1, &x2, &y2);
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d%d", &xx, &yy);
		p[i].d1 = dist(x1, yy1, xx, yy);
		p[i].d2 = dist(x2, y2, xx, yy);
	}
	sort(p + 1, p + n + 1, cmp);
	ans = p[n].d1; // 离第一个最远的  
	ans1 = -1e7; // 枚举离第二个最远的  
	for (int i = n - 1; i >= 1; --i) {
		ans1 = max(ans1, p[i + 1].d2);
		ans = min(ans, ans1 + p[i].d1);
	}
	printf("%d\n", ans);
	return 0;
}

这道题还是有一定的迷惑性的，只有考虑全情况，并且理性分析，才能写出最后正确的代码。