始终RE但是取出数据测试输出结果是正确的???有没有大佬帮忙看看!

P1429 平面最近点对(加强版)

13142180961cjk @ 2021-04-13 15:03:51

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();
    }

}

by 13142180961cjk @ 2021-04-13 15:04:14

我使用的是分治算法


|