本地输出240.5560(是正确答案),在其他电脑上答案却不一样。感觉也不是数组初始化的问题,我的电脑是macbook m1,洛谷各种编译选项都试过了,还是90分,过不去第六个点。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<map>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#define pb push_back
#define x first
#define y second
#define mkp make_pair
#define endl "\n"
using namespace std;
const int N = 1e4 + 10;
const double eps = 1e-6;
typedef long long ll;
typedef std::pair<int, int> PII;
typedef std::pair<ll, ll> PLL;
typedef std::pair<double, double> PDD;
int n;
double min_d;
PDD a[N];
double get(PDD a, PDD b){
double dx = a.x - b.x, dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
double dfs(int l, int r){
if(l >= r) return min_d;
int mid = (l + r) >> 1;
double ans = min(dfs(l, mid), dfs(mid + 1, r));
double midx = a[mid].x;
int i = l, j = mid + 1, cnt = 0;
vector<PDD> tmp;
while(i <= mid && j <= r){
if(a[i].y < a[j].y) tmp.pb(a[i++]);
else tmp.pb(a[j++]);
}
while(i <= mid) tmp.pb(a[i++]);
while(j <= r) tmp.pb(a[j++]);
for(int i = l; i <= r; i++)
a[i] = tmp[i - l];
tmp.clear();
cnt = 0;
for(int i = l; i <= r; i++){
if(a[i].x >= midx - ans && a[i].x <= midx + ans)
tmp.pb(a[i]);
}
for(int i = 0; i < tmp.size(); i++)
for(int j = i - 1; j >= 0 && tmp[i].y - tmp[j].y + eps <= ans; j--)
ans = min(ans, get(tmp[i], tmp[j]));
min_d = min(min_d, ans);
return ans;
}
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++){
double x, y;
scanf("%lf%lf", &x, &y);
a[i] = {x, y};
}
min_d = get(a[0], a[n - 1]);
sort(a, a + n);
double ans = dfs(0, n);
printf("%.4lf", ans);
return 0;
}
