救救我,81WAon #5#11
查看原帖
救救我,81WAon #5#11
300313
_luanyi_楼主2022/1/8 16:10

大众分治,不知道哪里挂了。
路过的神仙麻烦指教一下,谢谢。

#include <bits/stdc++.h>
#define fq(i,a,b) for (int i = (a); i <= (b); i++)
#define fnq(i,a,b) for (int i = (a); i < (b); i++)
#define nfq(i,a,b) for (int i = (a); i >= (b); i--)
#define nfnq(i,a,b) for (int i = (a); i > (b); i--)
#define fe(u) for (int i = head[u]; i; i = edge[i].nxt)
using namespace std;
#define int long long
inline int rd () {
	int f = 1;
	char ch = getchar ();
	while (!isdigit (ch)) (ch == '-' ? (f = -1) : 0), ch = getchar ();
	int num = 0;
	while (isdigit (ch)) num = num * 10 + ch - '0', ch = getchar ();
	return num * f;
}

//以上是 IO/宏

const int maxn = 200200;
const double inf = 4e9;
int n = rd ();
struct point {
	double x, y;
} p[maxn];
bool cmpx (point a, point b) {return a.x < b.x;}
bool cmpy (point a, point b) {return a.y < b.y;}
double dis (point a, point b) {
	return sqrt ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int pt[maxn], cnt;
double dv (int l, int r) {
	if (r - l + 1 == 1) return inf;
	if (r - l + 1 == 2) {
		if (p[l].y >= p[r].y) swap (p[l], p[r]);
		return dis (p[l], p[r]);
	}
	int mid = (l + r) >> 1;
	double d = min (dv (l, mid), dv (mid + 1, r));
	inplace_merge (p + 1, p + mid + 1, p + r + 1, cmpy);
	cnt = 0;
	int midx = p[mid].x;
	fq (i, l, r) if (fabs (p[i].x - midx) <= d) pt[++cnt] = i;
	int j = 1;
	fnq (i, 1, cnt) {
		while (j <= cnt && p[pt[j]].y <= p[pt[i]].y + d) ++j;
		fnq (m, i + 1, j) d = min (d, dis (p[pt[i]], p[pt[m]]));
	}
	return d;
	
}
signed main () {
	fq (i, 1, n) cin >>p[i].x>> p[i].y;
	sort (p + 1, p + n + 1, cmpx);
	printf ("%.4lf", dv (1, n));
	
	return 0;
}

2022/1/8 16:10
加载中...