2个wa,求调
查看原帖
2个wa,求调
1114140
yuniko_n楼主2024/3/30 14:34
//分治
import java.util.*;
import java.io.*;
public class Main{
	static int n;
	static double [][]a;//存储每个坐标
	static double [][]b;//存储处理跨中线坐标
	public static double dis(double x1,double y1,double x2,double y2) {//计算两点间距离方法
		return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
	}
	public static double merge(int l,int r) {//二分求解方法
		if(l==r)//只剩一个点,就返回无限大,也就是这个区间只有一个点
			return Double.MAX_VALUE;
		if(l+1==r)
			return dis(a[l][1],a[l][2],a[r][1],a[r][2]);
		
		int mid=(l+r)>>1;
		double d=Math.min(merge(l,mid), merge(mid+1,r));
		
		//每一次二分后的合并,都要进行跨中线处理
		int k=0;
		for(int i=l;i<=r;i++) {
			if(Math.abs(a[i][1]-a[mid][1])<d) {//三角关系
				k++;//横坐标距离比d小的存入b数组
				b[k][1]=a[i][1];
				b[k][2]=a[i][2];
			}
		}
		for(int i=1;i<=k;i++) {//对区间内所有点将进行判断
			for(int j=i+1;j<=k&&b[j][2]-b[i][2]<d;j++)
			    //b[j][2]-b[i][2]<d三角形三边关系
				//找出这个区间的最小距离
				d=Math.min(d,dis(b[i][1],b[i][2],b[j][1],b[j][2]));
		}
		return d;
	}
	public static void main(String[] args) throws IOException {
		StreamTokenizer sc=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
		sc.nextToken();
		n=(int)sc.nval;
		a=new double[n+1][3];
		b=new double[n+1][3];
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=2;j++) {
				sc.nextToken();
				a[i][j]=(double)sc.nval;
			}
		}
		//对二维数组排序,也就是对x进行排序
		Arrays.sort(a,Comparator.comparingDouble(a->a[1]));
		System.out.printf("%.4f",merge(1,n));
		out.flush();
	}
}
2024/3/30 14:34
加载中...