Emmmmm...
2024-08-28 21:55:18
发布于:上海
#include <iostream>
#include <algorithm> // The library that sort must call
using namespace std;
int x1,y1,x2,y2,n; // The five numbers entered are generated into global variables for the convenience of the cmp function
int d[100007]; // d array is preprocessed. See the idea for specific use
struct node
{
int x; // Record the position information of the missile
int y;
}w[100007];
bool cmp(node a,node b)
{
int q = (x1 - a.x) * (x1 - a.x) + (y1 - a.y) * (y1 - a.y);
int p = (x1 - b.x) * (x1 - b.x) + (y1 - b.y) * (y1 - b.y);
return q < p;
}
int main(void)
{
int ans = 0;
cin >> x1 >> y1 >> x2 >> y2;
cin >> n;
for (int i = 0;i < n;i++)
{
cin >> w[i].x >> w[i].y;
}
sort(w,w + n,cmp);
for (int i = n - 1;i >= 0;i--)
{
int h = (x2 - w[i].x) * (x2 - w[i].x) + (y2 - w[i].y) * (y2 - w[i].y); // Pretreatment process
d[i] = max(d[i + 1],h);
}
ans = d[0];
for (int i = 0;i < n;i++)
{
int cnt = 0;
cnt = (x1 - w[i].x) * (x1 - w[i].x) + (y1 - w[i].y) * (y1 - w[i].y);
cnt += d[i + 1]; // Since the maximum value reserved by d [i] includes i, i belongs to the prefix
ans = min(ans,cnt);
}
ans = min(ans,d[0]);
cout << ans;
return 0;
}
这里空空如也
有帮助,赞一个