Java 代码
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Acwing119 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int i=0;i<t;i++) {
int n = sc.nextInt();
Point[] points = new Point[n*2];
Point[] temp = new Point[n*2];
for (int j=0;j<n;j++){
points[j] = new Point(sc.nextInt(), sc.nextInt());
points[j].type=false;
}
for (int j=n;j<n<<1;j++){
points[j]=new Point(sc.nextInt(), sc.nextInt());
points[j].type=true;
}
Arrays.sort(points, Comparator.comparingInt(a -> a.x));
System.out.printf("%.3f\n", dfs(points, 0, (n<<1)-1, temp));
}
}
private static double dfs(Point[] points, int l, int r, Point[] temp) {
if (l==r) {
return Integer.MAX_VALUE;
}
int mid = l + r >> 1;
int midX = points[mid].x;
double ans = Math.min(dfs(points, l, mid, temp), dfs(points, mid+1, r, temp));
int i=l,j=mid+1,cnt=0;
while (i<=mid && j<=r) {
if (points[i].y<points[j].y) {
temp[cnt++]=points[i++];
} else {
temp[cnt++]=points[j++];
}
}
while (i<=mid) {
temp[cnt++]=points[i++];
}
while (j<=r) {
temp[cnt++]=points[j++];
}
for (i=l;i<=r;i++) {
points[i]=temp[i-l];
}
cnt=0;
for (i=l;i<=r;i++) {
if (points[i].x>=midX-ans && points[i].x<=midX+ans) {
temp[cnt++]=points[i];
}
}
for (i=0;i<cnt;i++) {
for (j=i-1;j>=0&&temp[i].y-temp[j].y<=ans;j--) {
ans = Math.min(ans, getDist(temp[i], temp[j]));
}
}
return ans;
}
private static double getDist(Point i, Point j) {
if (i.type == j.type) {
return Integer.MAX_VALUE;
}
double dx=i.x-j.x, dy=i.y-j.y;
return Math.sqrt(dx*dx+dy*dy);
}
}
class Point {
int x;
int y;
boolean type;
Point(int x, int y){
this.x=x;
this.y=y;
}
}