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
我使用的是分治算法