The challenge
Given a number of points on a plane, your task is to find two points with the smallest distance between them in linearithmicO[n log n]time.
Example
1 2 3 4 5 6 7 8 9
1
2 . A
3 . D
4 . F
5 . C
6
7 . E
8 . B
9 . G
For the plane above, the input will be:
[
[2,2], // A
[2,8], // B
[5,5], // C
[6,3], // D
[6,7], // E
[7,4], // F
[7,9] // G
]
=> closest pair is: [[6,3],[7,4]] or [[7,4],[6,3]]
[both answers are valid]
Code language: PHP [php]The two points that are closest to each other are D and F.
Expected answer should be an array with both points in any order.
Goal
The goal is to come up with a function that can find two closest points for any arbitrary array of points, in a linearithmic time.
Pointclass is preloaded for you as:
public class Point {
public double x, y;
public Point[] {
x = y = 0.0;
}
public Point[double x, double y] {
this.x = x;
this.y = y;
}
@Override
public String toString[] {
return String.format["[%f, %f]", x, y];
}
@Override
public int hashCode[] {
return Double.hashCode[x] ^ Double.hashCode[y];
}
@Override
public boolean equals[Object obj] {
if [obj instanceof Point] {
Point other = [Point] obj;
return x == other.x && y == other.y;
} else {
return false;
}
}
}
Code language: Java [java]More information onwikipedia.
The solution in Java code
Option 1:
import java.util.*;
import java.lang.*;
public class Solution {
public static List closestPair[List points] {
final List pair = new ArrayList[];
final List arr = new ArrayList[points];
arr.sort[[a, b] -> Double.valueOf[a.x].compareTo[Double.valueOf[b.x]]];
final int n = points.size[];
double l = Double.valueOf[Integer.MAX_VALUE];
double tolerance = Math.sqrt[l];
int a = 0, b = 0;
for [int i = 0; i + 1 < n; i++] {
for [int j = i + 1; j < n; j++] {
if [arr.get[j].x >= arr.get[i].x + tolerance] break;
final double ls = Math.pow[arr.get[i].x - arr.get[j].x, 2] + Math.pow[arr.get[i].y - arr.get[j].y, 2];
if [ls < l] {
l = ls;
tolerance = Math.sqrt[l];
a = i;
b = j;
}
}
}
pair.add[arr.get[a]];
pair.add[arr.get[b]];
return pair;
}
}
Code language: Java [java]Option 2:
import java.util.Arrays;
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public static List closestPair[List points] {
return divideAndConquer[points.stream[].sorted[[o1, o2] -> Double.compare[o1.x,o2.x]]
.collect[Collectors.toList[]].toArray[new Point[points.size[]]],points.size[]];
}
private static List divideAndConquer[Point[] pointSet, int size]{
if[size