萌新刚学分治,求助WA 18pts代码
查看原帖
萌新刚学分治,求助WA 18pts代码
482642
hank0402楼主2022/3/10 17:53

只AC了第二个点和第五个点,求助

#include<bits/stdc++.h>
using namespace std;
#define N 200005
const double Inf = 2000000007.0000;
struct node {
	double x, y;
}p[N];
int n;
bool cmp(node _x, node _y) {return _x.x < _y.x;}
bool ccmp(int _x, int _y) {return p[_x].y < p[_y].y;}
double dist(int _x, int _y) {return sqrt(1.0000 * (p[_x].x - p[_y].x) * (p[_x].x - p[_y].x) + 1.0000 * (p[_x].y - p[_y].y) * (p[_x].y - p[_y].y));}
double solve(int l, int r) {
	int mid = l + r >> 1, len = r - l + 1;
	if(len <= 2) return Inf;
	else if(len == 3) return dist(l, r) + dist(l + 1, r) + dist(l, r - 1);
	double d1 = solve(l, mid), d2 = solve(mid + 1, r);
	double d = min(d1, d2);
	double Min_ = d / 2.00000;
	vector<int> p1;
	for(int i = l; i <= r; ++i) {
		if(fabs(p[i].x - p[mid].x) <= (Min_)) p1.push_back(i);
	}
	sort(p1.begin(), p1.end(), ccmp);
	len = p1.size();
	for(int i = 0; i < len; ++i) {
		int lst;
		for(lst = 0; lst < len; ++lst) {
			if(fabs(p[p1[lst]].y - p[p1[i]].y) > (Min_)) break;
		}
		for(int j = i + 1; j < lst; ++j) {
			for(int k = i + 1; k < j; ++k) {
				d = min(d, dist(p1[i], p1[j]) + dist(p1[j], p1[k]) + dist(p1[i], p1[k]));
			}
		}
	}
	return d;
}
int main() {
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y;
	sort(p + 1, p + n + 1, cmp);
	printf("%0.6lf", solve(1, n));
	return 0;
} 
2022/3/10 17:53
加载中...