第一个点就wa了,输出92009.5964,54分求助啊,进来看看呗
查看原帖
第一个点就wa了,输出92009.5964,54分求助啊,进来看看呗
50497
weird_coder楼主2020/11/23 19:41
#include<stdio.h>
#include<string.h>
#include<math.h>
struct node
{
	double x, y;
}a[200005];
double distance(node a, node b)
{
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double min(double x,double y)
{
	return x < y ? x : y;
}
node s[200005];
int cnt = 0;
double ans = 3e10;
node t[200005];
void sort(int l, int r)
{
	int mid = (l + r) >> 1;
	if (l >= r) return;
	sort(l, mid);
	sort(mid + 1, r);
	int k = l;
	int i = l,j=mid+1;
	while (i<=mid&&j<=r)
	{
		if (a[i].y < a[j].y) t[k++] = a[i++];
		else t[k++] = a[j++];
	}
	while (i <= mid) t[k++] = a[i++];
	while (j <= r) t[k++] = a[j++];
	for (int i = l; i <= r; i++) a[i] = t[i];
}
void sort0(int l, int r)
{
	int mid = (l + r) >> 1;
	if (l >= r) return;
	sort(l, mid);
	sort(mid + 1, r);
	int k = l;
	int i = l, j = mid + 1;
	while (i <= mid && j <= r)
	{
		if (a[i].x < a[j].x) t[k++] = a[i++];
		else t[k++] = a[j++];
	}
	while (i <= mid) t[k++] = a[i++];
	while (j <= r) t[k++] = a[j++];
	for (int i = l; i <= r; i++) a[i] = t[i];
}
void merge(int l, int r)
{
	int mid = (l + r) >> 1;
	double dis;
	if (l == r) return;
	if (l + 1 == r)
	{
		dis = distance(a[l], a[r]);
		if (dis < ans) ans = dis;
		return;
	}
	merge(l, mid);
	merge(mid + 1, r);
	cnt = 0;
	for (int i = l; i <= r; i++)
	{
		if (fabs(a[i].x - a[mid].x) <= ans)
		{
			s[++cnt] = a[i];
		}
	}
	sort(1, cnt);
	for(int i=1;i<=cnt;i++)
		for (int j = i + 1; j <= cnt && s[j].y - s[i].y < ans; j++)
		{
			ans = min(distance(s[i],s[j]),ans);
		}
}
int main()
{
	freopen("a.txt","r",stdin);
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%lf%lf", &a[i].x, &a[i].y);
	sort0(1, n);
	merge(1, n);
	printf("%.4lf", ans);
	return 0;
}
2020/11/23 19:41
加载中...