wa了4个,求调
查看原帖
wa了4个,求调
1114140
yuniko_n楼主2024/3/29 21:16
//分治
import java.util.*;
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&&Math.abs(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) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		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++)
				a[i][j]=sc.nextInt();
		}
		//对二维数组排序,也就是对x进行排序
		Arrays.sort(a,new Comparator<double[]>() {
			public int compare(double []o1,double []o2) {
				return Double.compare(o1[1], o2[1]);
			}
		});
		System.out.printf("%.4f",ans);
	}
}
2024/3/29 21:16
加载中...