求助
查看原帖
求助
255850
ebubu楼主2021/6/11 14:12
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<math.h>
#include<algorithm>
using namespace std;
const int INF = 2 << 20;
struct point
{
	double x;
	double y;
};
point p[100000];
int temp[100000];

double dist(int i, int j)
{
	double x = (p[i].x - p[j].x) * (p[i].x - p[j].x);
	double y = (p[i].y - p[j].y) * (p[i].y - p[j].y);
	return sqrt(x + y);
}


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



bool cmp2(const int& a, const int& b)
{
	return p[a].y < p[b].y;
}

double min(double a, double b)
{
	return a < b ? a : b;
}


double merge(int left, int right)
{
	double d = INF;
	if (left == right)
		return d;
	if (left + 1 == right)
		return dist(left, right);

	int mid = left+right>>1;
	double l=merge(left, mid);
	double r=merge(mid + 1, right);
	d = min(1, r);

	int i, j, k = 0;
	for (i = left; i <= right; i++)
		if (fabs(p[mid].x-p[i].x) <= d)
			temp[k++] = i;


	sort(temp, temp + k, cmp2);


	for (i = 0; i < k; i++)
		for (j = i + 1; j < k && (p[temp[j]].y - p[temp[i]].y) < d; j++)
		{
			double m = dist(temp[i], temp[j]);
			if (d > m)
				d = m;
		}
	return d;
}


int main()
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> p[i].x >> p[i].y;

	sort(p, p + n, cmp);


	printf("%.4lf\n", merge(0, n - 1));


}

一直过不了 但是我感觉代码没错啊,帮帮忙。

2021/6/11 14:12
加载中...