2025-07-16 17:38:43
发布于：广东
1阅读
0回复
0点赞
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
struct Missile {
int d1_sq;
int d2_sq;
};
int main() {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int N;
cin >> N;
vector<Missile> missiles(N);
for (int i = 0; i < N; ++i) {
int x, y;
cin >> x >> y;
int dx1 = x - x1, dy1 = y - y1;
int dx2 = x - x2, dy2 = y - y2;
missiles[i].d1_sq = dx1 * dx1 + dy1 * dy1;
missiles[i].d2_sq = dx2 * dx2 + dy2 * dy2;
}
sort(missiles.begin(), missiles.end(), [](const Missile& a, const Missile& b) {
return a.d1_sq < b.d1_sq;
});
int min_cost = INT_MAX;
vector<int> max_d2_sq_from_end(N);
max_d2_sq_from_end[N - 1] = missiles[N - 1].d2_sq;
for (int i = N - 2; i >= 0; --i) {
max_d2_sq_from_end[i] = max(missiles[i].d2_sq, max_d2_sq_from_end[i + 1]);
}
min_cost = min(min_cost, missiles.back().d1_sq + 0);
int max_d2_sq = 0;
for (const auto& m : missiles) {
max_d2_sq = max(max_d2_sq, m.d2_sq);
}
min_cost = min(min_cost, 0 + max_d2_sq);
for (int i = 0; i < N - 1; ++i) {
int current_d1_sq = missiles[i].d1_sq;
int remaining_max_d2_sq = max_d2_sq_from_end[i + 1];
min_cost = min(min_cost, current_d1_sq + remaining_max_d2_sq);
}
cout << min_cost << " "<<endl;
return 0;
}
这里空空如也
有帮助，赞一个