WwwHx @ 2024-11-21 20:49:13
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
//两点之间的距离
double distance(const pair<double, double>& a, const pair<double, double>& b) {
return sqrt((a.first - b.first) * (a.first - b.first) +
(a.second - b.second) * (a.second - b.second));
}
//分治策略
double dfs(
const vector<pair<double, double>>& sortOfx,
int n, int l, int r) {
//最小域为一个点或者两个点
if (l == r || l > r)return INT_MAX; //同一个点不存在距离或者此域里没有点存在
if (l + 1 == r)return distance(sortOfx[l],sortOfx[r]); //相邻的点求出距离
// 1.寻找x的中点,将其分为两个域
int mid = l + ((r - l) >> 1);
double minr = dfs(sortOfx, n, mid, r);
double minl = dfs(sortOfx, n, l, mid - 1);
double finalyMin = min(minl, minr); //合并两个域的最小值
//2.求连通域的最小值 l保存左域的值 r保存右域的值
int temp[n], k = 0;
for (int i = l;i <= r;i++)if (fabs(sortOfx[i].first - sortOfx[mid].first) < finalyMin)temp[k++] = i;
for (int i = 0;i < k;i++) {
for (int j = i + 1;j < k ;j++) {
finalyMin = min(finalyMin, distance(sortOfx[temp[i]], sortOfx[temp[j]]));
}
}
return finalyMin;
}
int main() {
vector<pair<double, double>> point;
int n;
cin >> n;
for (int i = 0;i < n;i++) {
double x, y;cin >> x >> y;
point.push_back({ x,y });
}
vector<pair<double, double>> sortOfx(point); //按x轴从小到大排序
sort(sortOfx.begin(), sortOfx.end(), [](const pair<double, double>& a, const pair<double, double>& b) {
return a.first < b.first;
});
double ans = dfs(sortOfx,n, 0, n - 1);
printf("%.4f", ans);
}
加上排序只能过4个测试点,复杂度弄高了,所以其实区域内最小值集很少么,不需要筛选
by _just_a_OIer_LsQ_ @ 2024-11-21 20:56:01
@WwwHx 大佬的码风都这么像AI的吗()