附赠代码
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int T;

const double ran = 115.15215;

struct vec { double x, y; } ;

vec operator - (vec a, vec b) { return (vec) { a.x - b.x, a.y - b.y } ; }

double dis(vec a) { return sqrt(a.x * a.x + a.y * a.y); }

vec rota(vec a, double b)
{ return (vec) { cos(b) * a.x - sin(b) * a.y, sin(b) * a.x + cos(b) * a.y }; }

bool cmp(const vec &a, const vec &b)
{ return a.x == b.x ? a.y < b.y : a.x < b.x; }

vec a[100010];
vec b[100010];

int n;

int main()
{
    freopen("3714.in", "r", stdin);
    freopen("3714.out", "w", stdout);

    scanf("%d", &T);
    while (T--)
    {
	double ans = 1e11;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
	{
	    scanf("%lf%lf", &a[i].x, &a[i].y);
	    rota(a[i], ran);
	}
	for (int i = 1; i <= n; ++i)
	{
	    scanf("%lf%lf", &b[i].x, &b[i].y);
	    rota(b[i], ran);
	}
	
	sort(a + 1, a + n + 1, cmp);
	sort(b + 1, b + n + 1, cmp);

	int t = 1;
	for (int i = 1; i <= n; ++i)
	{
	    while (t < n && cmp(a[t + 1], b[i])) ++t;
	    for (int j = t; j <= n; ++j)
	    {
		if (fabs(a[j].x - b[i].x) > ans) break;
		ans = min(ans, dis(a[j] - b[i]));
	    }
	    for (int j = t - 1; j; --j)
	    {
		if (fabs(a[j].x - b[i].x) > ans) break;
		ans = min(ans, dis(a[j] - b[i]));
	    }
	}
	printf("%.3f\n", ans);
    }
    return 0;
}
	
    

• 为什么不是kdtree (0) lllllllllllll 2014-06-06 16:35:56
• Re:请不要想复杂了，对付最近点对最好的办法永远是旋转坐标系＋O(n^2)暴力 (1586) pwfange 2021-11-08 20:30:22
• Re:请不要想复杂了，对付最近点对最好的办法永远是旋转坐标系＋O(n^2)暴力 (1586) u20215570 2022-12-08 22:13:22