WA两个, 求助, 感谢
查看原帖
WA两个, 求助, 感谢
689146
mushezi楼主2023/3/28 13:18
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

struct point{
	double x, y;
} a[N], b[N];

bool cmpx(point & a, point & b){
	if(a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}

double dist(point & a, point & b){
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	return sqrt(dx * dx + dy * dy);
}

double solve(int l, int r){
	if(l == r) return 2e9;
	int mid = (l + r) >> 1;
	double d = min(solve(l, mid), solve(mid + 1, r));
	point cur = a[mid];
	
	{
		int i = l, j = mid + 1, k = 0;
		while(i <= mid && j <= r){
			if(a[i].y < a[j].y) b[++k] = a[i++];
			else b[++k] = a[j++]; 
		}
		while(i <= mid) b[++k] = a[i++];
		while(j <= r) b[++k] = a[j++];
		
		for(int t = l; t <= r; t++){
			a[t] = b[t - l + 1];
		}
	}
	
	int k = 0;
	for(int i = l; i <= r; i++){
		if(abs(a[i].x - cur.x) < d) b[++k] = a[i];
	}
	
	for(int i = 1; i < k; i++){
		for(int j = i + 1; j <= k && abs(b[j].y - b[i].y) < d; j++){
			d = min(d, dist(b[i], b[j]));
		}
	}
	
	return d;
}

int n;
double x, y;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> x >> y;
		a[i] = {x, y};
	}
	
	sort(a + 1, a + n + 1, cmpx);
	
	cout << fixed << setprecision(4) << solve(1, n);
	
	return 0;
}
2023/3/28 13:18
加载中...