专栏文章

题解：P1158 [NOIP2010 普及组] 导弹拦截

HHeart_of_Iron
P1158题解参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miqkfqcc
此快照首次捕获于
2025/12/04 06:15
3 个月前
此快照最后确认于
2025/12/04 06:15
3 个月前
查看原文

思路

贪心！用公式 (x1−x)2+(y1−y)2(x1-x)^2+(y1-y)^2 把它放进结构体 d[i].d1 ，(x2−x)2+(y2−y)2(x2-x)^2+(y2-y)^2 把它放进结构体 d[i].d2。然后 sort 一下让 r12+r22r_1{^2}+r_2{^2} 最小，然后定义一个结构体数组存 r1r_1 和 r2r_2，然后从大到小排序，最后 ans=min(d[i+1].d1+r2,ans); 一下就行了（ans 的值需要很大）。

警示后人

用了万能头不能用 x1,x2,y1,y2 之类的变量。所以我才用 define。

代码

CPP
#include<bits/stdc++.h>
#define x1 X1
#define x2 X2
#define y1 Y1
#define y2 Y2
#define int long long
using namespace std;
int x1,x2,y1,y2,r1,r2,ans=0x3ffffffff,n;
struct node
{
	int d1,d2;
}d[114514];
bool cmp(node x,node y)
{
	return x.d1>y.d1;
}
signed main() 
{
	cin >> x1 >> y1 >> x2 >> y2 >> n;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin >> x >> y;
		d[i].d1=(x1-x)*(x1-x)+(y1-y)*(y1-y);
		d[i].d2=(x2-x)*(x2-x)+(y2-y)*(y2-y);
	}
	sort(d+1,d+n+1,cmp);
	ans=d[1].d1;
	for(int i=1;i<=n;i++)
	{
		r2=max(r2,d[i].d2);
		ans=min(d[i+1].d1+r2,ans);
	}
	cout << ans;
	return 0;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...