萌新刚学,求大佬解答为什么本蒟蒻的写法会需要跑两遍函数
查看原帖
萌新刚学,求大佬解答为什么本蒟蒻的写法会需要跑两遍函数
912603
yu18250787255楼主2025/8/1 20:46

Rt,是有什么没有在第一次跑的时候先处理好吗?

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;

struct Node
{
	double x;
	double y; 
}arr[200005],brr[200005];
bool cmp(int a,int b)
{
	return arr[a].y<arr[b].y;
}
int temp[200005];
double dis(Node a,Node b)
{
	return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
double quick_sort(int l,int r)
{
	if(l>=r)
	{
		return 2e9;
	}
	int mid=l+r>>1;
	double d=min(quick_sort(l,mid),quick_sort(mid+1,r));
	int p1=l,p2=mid+1,k=l;
	while(p1<=mid && p2<=r)
	{
		if(arr[p1].x<arr[p2].x)
		{
			brr[k]=arr[p1];
			p1++;
		}else
		{
			brr[k]=arr[p2];
			p2++;
		}
		k++;
	}
    while(p1<=mid)
    {
        brr[k]=arr[p1];
        k++;
        p1++;
    }
    while(p2<=r)
    {
    	brr[k]=arr[p2];
        k++;
        p2++;
    }
	for(int i=l;i<=r;i++)
	{
		arr[i]=brr[i];
	}
	temp[0]=0;
	for(int i=l;i<=r;i++)
	{
		if(fabs(arr[mid].x-arr[i].x)<d)
		{
			temp[0]++;
			temp[temp[0]]=i;
		}
	}
	sort(temp+1,temp+temp[0]+1,cmp);
	for(int i=1;i<=temp[0];i++)
	{
		for(int j=i+1;j<=temp[0] && arr[temp[j]].y-arr[temp[i]].y<d;j++)
		{
			d=min(d,dis(arr[temp[i]],arr[temp[j]]));
		}
	}
	return d;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>arr[i].x>>arr[i].y;
	}
	quick_sort(1,n);
	printf("%.4lf",quick_sort(1,n));
	return 0;
}
2025/8/1 20:46
加载中...