phenomenonsTell 于 2017.09.13 20:05 提问

HDOJ 1007 使用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;
}
}
}

``````