始终RE但是取出数据测试输出结果是正确的???有没有大佬帮忙看看!
查看原帖
始终RE但是取出数据测试输出结果是正确的???有没有大佬帮忙看看!
261959
13142180961cjk楼主2021/4/13 15:03
package DivideandConquer;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;


class point{
	double x;
	double y;
}

 class Closestpairofpoints {
    public static double sq(point a,point b) {
    	return Math.sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
    
	public static double Closestpoint(point []a,int start,int end) {
		
		
		if(start==end) {
			return -1;
		}
		if(end-start==1) {
			return sq(a[start],a[end]);
		}
		int mid=(start+end)/2;
		double d1=Closestpoint(a,start,mid);
		double d2=Closestpoint(a,mid+1,end);
		double d=100000000;
		if(d1>0&&d2>0)
		d=Math.min(d1,d2);
		else if(d1>0)d=d1;
		else if(d2>0)d=d2;
		int index1=0;
		for(int i=start;i<mid;i++) {
			if(Math.abs(a[i].x-a[mid].x)<d) {
				index1++;
			}
		}
		point []P1=new point[index1];
		index1=0;
		for(int i=start;i<mid;i++) {
			if(Math.abs(a[i].x-a[mid].x)<d) {
				P1[index1]=new point();
				P1[index1].x=a[i].x;
				P1[index1].y=a[i].y;
				index1++;
			}
		}
		int index2=0;
		for(int i=mid;i<=end;i++) {
			if(Math.abs(a[i].x-a[mid].x)<d) {
				index2++;
			}
		}
		point []P2=new point[index2];
		index2=0;
		for(int i=mid;i<=end;i++) {
			if(Math.abs(a[i].x-a[mid].x)<d) {
				P2[index2]=new point();
				P2[index2].x=a[i].x;
				P2[index2].y=a[i].y;
				index2++;
			}
		}
		Arrays.sort(P1,new Comparator<point>() {
			public int compare(point a,point b) {
				int k=(int)(b.y-a.y);
				return k;
			}
		});
		Arrays.sort(P2,new Comparator<point>() {
			public int compare(point a,point b) {
				int k=(int)(b.y-a.y);
				return k;
			}
		});
		for(int i=0;i<index1;i++) {
			for(int j=0;j<index2&&j<6;j++) {
				if(sq(P1[i],P2[j])<d){
					d=sq(P1[i],P2[j]);
				}
			}
		}
		return d;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
        point []s=new point[n];
        for(int i=0;i<n;i++) {
        	s[i]=new point();
        	s[i].x=in.nextDouble();
        	s[i].y=in.nextDouble();
        }
        Arrays.sort(s,new Comparator<point>() {
			public int compare(point a,point b) {
				int k=(int)(a.x-b.x);
				return k;
			}
		});
        double k=Closestpoint(s,0,n-1);
        System.out.printf("%.4f\n",k);
        in.close();
	}

}

2021/4/13 15:03
加载中...