为什么第一个样例本地是对的,提交就WA了?
查看原帖
为什么第一个样例本地是对的,提交就WA了?
457431
Li_wenjie楼主2022/5/29 23:12

2 22990 6691 37281 24938 ANS:23177.2667 本地:23177.2667

#include<bits/stdc++.h>
using namespace std;
typedef double D;
const int N=1e4+1;
struct Node
{
	int x,y;
}a[N];
D ans=2e9+0.01;
bool cmp(Node a,Node b)
{
	return a.x<b.x;
}
D dis(Node a,Node b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
D solve(int l,int r)
{
	if(r==l+1)
	{
		ans=min(ans,dis(a[r],a[l]));
		return dis(a[r],a[l]);
	 } 
	 else if(r==l)
	 {
	 	return 2e9+0.01;
	 }
	 int mid=(l+r)>>1;
	 D p=min(solve(mid,r),solve(l,mid-1));
	 int ll=mid,rr=mid;
	 while(a[mid].x-a[ll].x<=p&&ll>l) ll--;
	 while(a[rr].x-a[mid].x<=p&&rr<r) rr++;
	 for(int i=ll;i<=mid;i++)
	 	for(int j=mid;j<=rr;j++)
	 	{
	 		p=min(p,dis(a[i],a[j]));
		 }
	ans=min(ans,p);
	return p;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	sort(a+1,a+n+1,cmp);
	solve(1,n);
	printf("%.4llf",ans);
}
2022/5/29 23:12
加载中...