[NOIP2010]导弹拦截

第一行包含4个整数x₁、y₁、x₂、y₂，每两个整数之间用一个空格隔开，表示这两套导弹拦截系统的坐标分别为(x₁, y₁)、(x₂, y₂)。

第二行包含1个整数N，表示有N颗导弹。接下来N行，每行两个整数x、y，中间用一个空格隔开，表示一颗导弹的坐标(x, y)。不同导弹的坐标可能相同。

Python3 解法, 执行用时: 662ms, 内存消耗: 25340K, 提交时间: 2022-03-05 00:30:11

x_y = list(map(int, input().split()))
m = int(input())
dp = []
for i in range(m):
    a, b = map(int, input().split())
    c = (a-x_y[0])**2+(b-x_y[1])**2
    dp.append([a, b, c])
dp.sort(key= lambda x:x[2], reverse=True)
# print(dp, dp_1)
a, b = dp[0][2], 0
for i in range(1, m):
    b = max(b, (dp[i-1][0]-x_y[2])**2+(dp[i-1][1]-x_y[3])**2)
    a = min(a, b+dp[i][2])
print(a)

C++(g++ 7.5.0) 解法, 执行用时: 50ms, 内存消耗: 2032K, 提交时间: 2023-07-18 16:19:46

#include<bits/stdc++.h>
using namespace std;
pair<int,int>m[100005];
int main()
{
    int x1,x2,y1,y2,x,y,n,i,t=0,s=2e7;
	cin>>x1>>y1>>x2>>y2>>n;
	for(i=0;i<n;i++){
		cin>>x>>y;
		m[i].first=pow(x-x1,2)+pow(y-y1,2);
		m[i].second=pow(x-x2,2)+pow(y-y2,2); 
	}
	sort(m,m+n);
	for(i=n-1;i>=0;i--){
		s=min(s,m[i].first+t);
		t=max(t,m[i].second);
	}
	cout<<min(s,t);
}

C++11(clang++ 3.9) 解法, 执行用时: 74ms, 内存消耗: 1256K, 提交时间: 2020-02-15 18:54:42

#include<bits/stdc++.h>
using namespace std;
int A,B,C,D,x,y,n,i,t=0,s=2e7;
pair<int,int>m[100005];
int main()
{
	cin>>A>>B>>C>>D>>n;
	for(i=0;i<n;i++)
	{
		cin>>x>>y;
		m[i].first=pow(x-A,2)+pow(y-B,2);
		m[i].second=pow(x-C,2)+pow(y-D,2); 
	}
	sort(m,m+n);
	for(i=n-1;i>=0;i--)
	{
		s=min(s,m[i].first+t);
		t=max(t,m[i].second);
	}
	cout<<min(s,t);
}

详情