2 phenomenonstell phenomenonsTell 于 2017.09.13 20:05 提问

HDOJ 1007 使用java解题一直运行超时

不管我用暴力破解还是采取分治法都一直运行超时,网上的解法全是C/C++的,没有Java的
哪位大神可以指点一下啊
附代码:

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



public class p1007 {

    private static Point[] p;

    private static Point[] tmp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            if(n == 0) break;
            p = new Point[n];
            tmp = new Point[n];
            for(int i = 0;i<n;i++) {
                p[i] = new Point(sc.nextFloat(), sc.nextFloat());

            }
            Arrays.sort(p, new Comparator<Point>() {

                @Override
                public int compare(Point o1, Point o2) {
                    if(o1.x<o2.x)
                        return -1;
                    else
                        if(o1.x == o2.x) {
                            if(o1.y<o2.y)
                                return -1;
                            else
                                return 1;
                        }
                        return 1;
                }

            });
            double res = minDistance(0, n-1);
            System.out.printf("%.2f", res);
            System.out.println();

        }
        sc.close();
    }

    public static double minDistance(int left, int right) {

        if(left == right) 
            return 0;
        else if(left + 1 == right) 
            return Math.sqrt(distance(p[left], p[right]))/2;
        else if(left + 2 == right) 
            return Math.sqrt(min(min(distance(p[left], p[left+1]), distance(p[left+1], p[right])), distance(p[left], p[right])))/2;

        int mid = (left + right)/2;
        int index = 0;
        int pointer = 0;

        double minDis = min(min(minDistance(left, mid), minDistance(mid+1, right)), minDistance(mid, mid+1));
        for(int i = 0;i<right;i++) {
            if(Math.abs(p[i].x - p[right].x)<minDis) {
                tmp[index++] = p[i];
                pointer = i;
            }
        }
        if(index == 0)
            return minDis;
        if(index == 1)
            for(int i = 0;i<right && i!=pointer;i++) {
                double dis = Math.sqrt(distance(tmp[0], p[i]))/2;
                if(dis<minDis) {
                    minDis = dis;
                    break;
                }   
            }
        if(index>1) {

            for(int i = 0;i<index;i++) {
                for(int j = i+1;j<index && tmp[i].y - tmp[j].y <minDis;j++) {
                    minDis = min(minDis, Math.sqrt(distance(tmp[i], tmp[j]))/2);
                }
            }
        }
        return minDis;
    }

    public static double min(double a, double b) {
        if(a<b)
            return a;
        else
            return b;
    }

    public static double distance(Point a, Point b) {
        float x = a.x - b.x;
        float y = a.y - b.y;
        return x*x+y*y;
    }

    static class Point {

        private float x;

        private float y;

        public Point(float x, float y) {
            this.x = x;
            this.y = y;
        }
    }
}

Csdn user default icon
上传中...
上传图片
插入图片