好哥哥们,思路应该是对的。为啥会tle啊
查看原帖
好哥哥们,思路应该是对的。为啥会tle啊
255951
Myzc楼主2023/3/7 13:42


#include <bits/stdc++.h>

const int N = 2e5 + 5;
struct Node{
	Node(long long x, long long y): x(x), y(y) {}
	Node() {}
	long long x;
	long long y;
	
	bool operator < (const Node &t) const{
		if(x == t.x) {
			return x < t.x;
		}
		return x < t.x;
	}
}node[N];
int n;
int temp[N];

bool cmpy(const int &n1,const int &n2) {
	return node[n1].y < node[n2].y;
}

long long dis(const Node &n1,const Node &n2) {
	return (n1.x - n2 .x) * (n1.x - n2.x) +
		(n1.y - n2.y) * (n1.y - n2.y);
}

long long cal(int l, int r) {
	//std::cout << "l = " << l << ' ' << "r = " << r << '\n'; 
	if(l >= r) {
		return 0x3f3f3f3f3f3f3f3f;
	} else if(l + 1 == r) {
		return dis(node[l], node[r]);
	}
	
	int mid = (l + r) >> 1;
	long long lDis = cal(l, mid);
	long long rDis = cal(mid + 1, r);
	
	long long d = std::min(lDis, rDis);
	//std::cout << l << ' ' << r << ' ' << d << '\n';
	
	int sz = 0;
	for(int i = l; i <= r; i++){
		if(fabs(node[mid].x - node[i].x) < d) {
			temp[sz++] = i;
		}
	}
	
	std::sort(temp, temp + sz, cmpy);
	long long d1 = d;
	
	for(int i = 0; i < sz; i++) {
		for(int j = i + 1; j < sz && node[temp[j]].y - node[temp[i]].y < d; j++) { 
			d1 = std::min(d1, dis(node[temp[i]], node[temp[j]]));
		}
	}
	
	return d1;
}

int main() {
	std::cin >> n;
	
	for(int i = 0; i < n; i++) {
		scanf("%d %d", &node[i].x, &node[i].y);
	}
	
	std::sort(node, node + n);
	long long ans = cal(0, n - 1);
	
	printf("%.4lf\n", sqrt(ans) );
	
	return 0;
}

2023/3/7 13:42
加载中...