1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
public class CloestDistance {
public static class Point {
long x, y;
public Point(long x, long y) {
this.x = x;
this.y = y;
}
}
public static class XComparator implements Comparator<Point> {
@Override
public int compare(Point p0, Point p1) {
return p0.x == p1.x ? Long.signum(p0.y - p1.y) : Long.signum(p0.x - p1.x);
}
}
public static class YComparator implements Comparator<Point> {
@Override
public int compare(Point p0, Point p1) {
return p0.y == p1.y ? Long.signum(p0.x - p1.x) : Long.signum(p0.y - p1.y);
}
}
public static double minimalDistance(int[] x, int[] y) {
Point[] ptsArray = new Point[x.length];
for (int i = 0; i < ptsArray.length; i++) {
ptsArray[i] = new CloestDistance.Point(x[i], y[i]);
}
Arrays.sort(ptsArray, new CloestDistance.XComparator());
return minimalDistance(ptsArray, 0, ptsArray.length - 1);
}
private static double minimalDistance(Point[] ptsArray, int low, int high) {
if (high - low <= 3) {
return baseCaseMinDistance(ptsArray, low, high);
}
int mid = low + (high - low) / 2;
long midX = ptsArray[mid].x;
double d1 = minimalDistance(ptsArray, low, mid - 1);
double d2 = minimalDistance(ptsArray, mid, high);
double d = Math.min(d1, d2);
List<Point> shadedPoints = new ArrayList<Point>();
for (int i = low; i <= high; i++) {
if (Math.abs(ptsArray[i].x - midX) <= d)
shadedPoints.add(ptsArray[i]);
}
shadedPoints.sort(new YComparator());
double dPrime = dPrimeDistance(shadedPoints);
return Math.min(d, dPrime);
}
private static double dPrimeDistance(List<Point> shadedPoints) {
double minDistance = Double.MAX_VALUE;
double tempDistance;
for (int i = 0; i < shadedPoints.size(); i++) {
for (int j = 1; j <= 7; j++) {
if (i + j < shadedPoints.size()) {
tempDistance = distance(shadedPoints.get(i), shadedPoints.get(i + j));
minDistance = Math.min(tempDistance, minDistance);
}
}
}
return minDistance;
}
private static double baseCaseMinDistance(Point[] ptsArray, int low, int high) {
if (high - low == 1)
return distance(ptsArray[low], ptsArray[high]);
if (high - low == 2) {
double d1 = distance(ptsArray[low], ptsArray[low + 1]);
double d2 = distance(ptsArray[low], ptsArray[high]);
double d3 = distance(ptsArray[high], ptsArray[low + 1]);
return Math.min(d1, Math.min(d2, d3));
}
double d1 = distance(ptsArray[low], ptsArray[low + 1]);
double d2 = distance(ptsArray[low], ptsArray[low + 2]);
double d3 = distance(ptsArray[low], ptsArray[high]);
double d4 = distance(ptsArray[low + 1], ptsArray[low + 2]);
double d5 = distance(ptsArray[low + 1], ptsArray[high]);
double d6 = distance(ptsArray[low + 2], ptsArray[high]);
return Math.min(d1, Math.min(d2, Math.min(d3, Math.min(d4, Math.min(d5, d6)))));
}
public static double distance(Point p1, Point p2) {
return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
public static void main(String[] args) throws Exception {
reader = new BufferedReader(new InputStreamReader(System.in));
writer = new PrintWriter(System.out);
int n = nextInt();
int[] x = new int[n];
int[] y = new int[n];
for (int i = 0; i < n; i++) {
x[i] = nextInt();
y[i] = nextInt();
}
System.out.println(minimalDistance(x, y));
writer.close();
}
static BufferedReader reader;
static PrintWriter writer;
static StringTokenizer tok = new StringTokenizer("");
static String next() {
while (!tok.hasMoreTokens()) {
String w = null;
try {
w = reader.readLine();
} catch (Exception e) {
e.printStackTrace();
}
if (w == null)
return null;
tok = new StringTokenizer(w);
}
return tok.nextToken();
}
static int nextInt() {
return Integer.parseInt(next());
}
}
|
