Tasks Details
hard
Given a set of points on a cartesian plane, find the minimum distance between some pair of them to maximise another metric.
Task Score
100%
Correctness
100%
Performance
100%
There are N sheep relaxing in a field. They are positioned at points with integer coordinates. Each sheep has a square sunshade, so as not to overheat. The sunshade of a sheep standing at position (X, Y) spreads out to a distance of D from (X, Y), covering a square whose middle is at (X, Y) and whose sides are of length 2D. More precisely, it covers a square with vertices in points (X − D, Y − D), (X − D, Y + D), (X + D, Y − D) and (X + D, Y + D). Sheep are in the centres of their sunshades. Sunshades edges are parallel to the coordinate axes.
Every sheep spreads out its sunshade to the same width. No two sunshades can overlap, but their borders can touch.
What is the maximum integer width D to which the sheep can spread out their sunshades?
Write a function:
class Solution { public int solution(int[] X, int[] Y); }
that, given two arrays X and Y of length N denoting the positions of the sheep, returns the maximum value of D to which the sheep can spread out their sunshades. There are at least two sheep in the flock, and no two sheep share a point with the same coordinates.
Examples:
1. Given X=[0, 0, 10, 10] and Y=[0, 10, 0, 10],
the function should return 5.
2. Given X=[1, 1, 8] and Y=[1, 6, 0],
the function should return 2.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [2..100,000];
- each element of arrays X and Y is an integer within the range [0..100,000];
- no two sheep are standing in the same position.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 21
Time spent on task 1 minutes
Notes
not defined yet
Code: 22:16:10 UTC,
java,
autosave
Code: 22:16:15 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290
package codility.rubidium;
import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
// implement point comparable by x ... w function distance to ...
class MyPoint extends Point implements Comparable<MyPoint> {
public MyPoint(int x, int y){
this.x = x ;
this.y = y ;
}
@Override
public String toString(){
return "x:"+this.x + ",y:" +this.y ;
}
@Override
public int compareTo(MyPoint o) {
if(this.x == o.x){
return this.y - o.y ;
}
return this.x - o.x ;
}
}
class ClosestPairCustom {
// closest pair of points and their Euclidean distance
private MyPoint best1, best2;
private MyPoint nearestToBest1, nearestToBest2;
private int bestDistance = Integer.MAX_VALUE;
double point1Distance = Double.MAX_VALUE;
double point2Distance = Double.MAX_VALUE;
public ClosestPairCustom(MyPoint[] points) {
int n = points.length;
if (n <= 1) return;
// sort by x-coordinate (breaking ties by y-coordinate)
Arrays.sort(points);
// check for co-incident points
for (int i = 0; i < n-1; i++) {
if (points[i].equals(points[i+1])) {
bestDistance = 0;
best1 = points[i];
best2 = points[i+1];
return;
}
}
// sort by y-coordinate (but not yet sorted)
MyPoint[] pointsByY = new MyPoint[n];
for (int i = 0; i < n; i++)
pointsByY[i] = points[i];
// auxiliary array
MyPoint[] aux = new MyPoint[n];
closest(points, pointsByY, aux, 0, n-1);
}
// find closest pair of points in points[lo..hi]
// precondition: points[lo..hi] and pointsByY[lo..hi] are the same sequence of points
// precondition: points[lo..hi] sorted by x-coordinate
// postcondition: pointsByY[lo..hi] sorted by y-coordinate
private int closest(MyPoint[] pointsByX, MyPoint[] pointsByY, MyPoint[] aux, int lo, int hi) {
if (hi <= lo) return Integer.MAX_VALUE;
int mid = lo + (hi - lo) / 2;
MyPoint median = pointsByX[mid];
// compute closest pair with both endpoints in left subarray or both in right subarray
int delta1 = closest(pointsByX, pointsByY, aux, lo, mid);
int delta2 = closest(pointsByX, pointsByY, aux, mid+1, hi);
int delta = Math.min(delta1, delta2);
// merge back so that pointsByY[lo..hi] are sorted by y-coordinate
merge(pointsByY, aux, lo, mid, hi);
// aux[0..m-1] = sequence of points closer than delta, sorted by y-coordinate
int m = 0;
for (int i = lo; i <= hi; i++) {
if (distanceTo(pointsByY[i], median) < delta)
aux[m++] = pointsByY[i];
}
// compare each point to its neighbors with y-coordinate closer than delta
for (int i = 0; i < m; i++) {
// a geometric packing argument shows that this loop iterates at most 7 times
for (int j = i+1; (j < m) && (distanceTo(aux[j], aux[i]) < delta); j++) {
int distance = distanceTo(aux[i], aux[j]);
if (distance < delta) {
delta = distance;
if (distance < bestDistance) {
bestDistance = delta;
best1 = aux[i];
best2 = aux[j];
}
}
}
}
return delta;
}
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
public MyPoint either() {
return best1;
}
public MyPoint other() {
return best2;
}
public double distance() {
return bestDistance;
}
public int distanceTo(MyPoint p1, MyPoint p2){
return Math.max(Math.abs(p1.x - p2.x)/2, Math.abs(p1.y - p2.y)/2) ;
//return Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2) ;
}
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public int bruteForce(List<MyPoint> points) {
Point p1 = null ;
Point p2 = null ;
double distanceResult = Double.MAX_VALUE ;
int numPoints = points.size();
if (numPoints < 2)
return 0;
if (numPoints >= 2) {
for (int i = 0; i < numPoints - 1; i++) {
MyPoint point1 = points.get(i);
for (int j = i + 1; j < numPoints; j++) {
MyPoint point2 = points.get(j);
double distance = this.distanceTo(point1, point2);
if (distance < distanceResult){
distanceResult = distance ;
p1 = point1 ;
p2 = point2 ;
}
}
}
}
//System.out.println("brute points found " + p1 + " " + p2);
return Math.max(Math.abs(p1.x - p2.x)/2, Math.abs(p1.y - p2.y)/2) ;
}
public int finalCheck(MyPoint[] points, MyPoint p1 , MyPoint p2, int delta){
for (int i = 0; i < points.length; i++) {
if (!points[i].equals(p1) && distanceTo(points[i], p1) < delta){
return distanceTo(points[i], p1) ;
}
if (!points[i].equals(p2) && distanceTo(points[i], p2) < delta){
return distanceTo(points[i], p2) ;
}
}
return delta ;
}
}
public class Sheeps {
public int solution(int[] X, int[]Y){
MyPoint[] points = new MyPoint[X.length] ;
for(int i = 0 ; i < X.length ; i++){
points[i] = new MyPoint(X[i], Y[i]) ;
}
ClosestPairCustom cp = new ClosestPairCustom(points) ;
//System.out.println("cp points found " + cp.other() + " " + cp.either());
int D = Math.max(Math.abs(cp.either().x - cp.other().x)/2, Math.abs(cp.either().y - cp.other().y)/2) ;
D = Math.min(cp.finalCheck(points, cp.either(), cp.other(), D), D);
return D;
}
public int solutionBrute(int[] X, int[]Y){
List<MyPoint> pointsList = new ArrayList<MyPoint>() ;
MyPoint[] points = new MyPoint[X.length] ;
for(int i = 0 ; i < X.length ; i++){
points[i] = new MyPoint(X[i], Y[i]) ;
pointsList.add(new MyPoint(X[i], Y[i])) ;
}
ClosestPairCustom cp = new ClosestPairCustom(points) ;
return cp.bruteForce(pointsList) ;
}
// remove ...
public boolean drawGrid(int D, int[] X, int[]Y){
HashSet<MyPoint> cornersTakenAlready = new HashSet<MyPoint>() ;
for(int i = 0 ; i < X.length ; i++){
if(!drawSquareCorners(cornersTakenAlready, X[i], Y[i], D)){
return false ;
}
}
return true ;
// int[][] grid = new int[this.grid_side+50][this.grid_side+50];
// for(int h = 0 ; h < grid.length ; h++){
// Arrays.fill(grid[h], -1);
// }
// for(int i = 0 ; i < X.length ; i++){
// if(!drawSquare(grid, X[i], Y[i], D, i)){
// return false ;
// }
// }
// return true ;
// for(int i = 0 ; i < grid.length ; i++){
// System.out.println(Arrays.toString(grid[i]));
// }
}
public boolean drawSquare(int[][] grid, int x, int y, int d, int i){
//directions in the 3rd dimension : 0 left ... 1 right ... 2 up ... 3 down
for(int l = x-d ; l < x+d ; l++){
for(int m = y-d ; m < y+d ; m++){
if(l > -1 && l < grid.length && m > -1 && m < grid[0].length){
if(grid[l][m] != -1 && grid[l][m] != i){
System.out.println("Intersection at " + l + " " + m + " between " + grid[l][m] + " and " + i);
return false;
}
grid[l][m] = i ;
}
}
}
return true ;
}
public boolean drawSquareCorners(Set<MyPoint> corners, int x, int y, int d){
MyPoint corner1 = new MyPoint(x-d, y-d) ;
MyPoint check_1 = new MyPoint(x-d+1, y-d+1) ;
MyPoint corner2 = new MyPoint(x-d, y+d) ;
MyPoint check_2 = new MyPoint(x-d+1, y+d-1) ;
MyPoint corner3 = new MyPoint(x+d, y-d) ;
MyPoint check_3 = new MyPoint(x+d-1, y-d+1) ;
MyPoint corner4 = new MyPoint(x+d, y+d) ;
MyPoint check_4 = new MyPoint(x+d-1, y+d-1) ;
if(corners.contains(check_1) || corners.contains(check_2) || corners.contains(check_3) || corners.contains(check_4)){
return false ;
}
corners.add(corner1) ;
corners.add(corner2) ;
corners.add(corner3) ;
corners.add(corner4) ;
corners.add(check_1) ;
corners.add(check_2) ;
corners.add(check_3) ;
corners.add(check_4) ;
return true ;
}
}
Code: 22:16:26 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225
package codility.rubidium;
import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
// implement point comparable by x ... w function distance to ...
class MyPoint extends Point implements Comparable<MyPoint> {
public MyPoint(int x, int y){
this.x = x ;
this.y = y ;
}
@Override
public String toString(){
return "x:"+this.x + ",y:" +this.y ;
}
@Override
public int compareTo(MyPoint o) {
if(this.x == o.x){
return this.y - o.y ;
}
return this.x - o.x ;
}
}
class ClosestPairCustom {
// closest pair of points and their Euclidean distance
private MyPoint best1, best2;
private MyPoint nearestToBest1, nearestToBest2;
private int bestDistance = Integer.MAX_VALUE;
double point1Distance = Double.MAX_VALUE;
double point2Distance = Double.MAX_VALUE;
public ClosestPairCustom(MyPoint[] points) {
int n = points.length;
if (n <= 1) return;
// sort by x-coordinate (breaking ties by y-coordinate)
Arrays.sort(points);
// check for co-incident points
for (int i = 0; i < n-1; i++) {
if (points[i].equals(points[i+1])) {
bestDistance = 0;
best1 = points[i];
best2 = points[i+1];
return;
}
}
// sort by y-coordinate (but not yet sorted)
MyPoint[] pointsByY = new MyPoint[n];
for (int i = 0; i < n; i++)
pointsByY[i] = points[i];
// auxiliary array
MyPoint[] aux = new MyPoint[n];
closest(points, pointsByY, aux, 0, n-1);
}
// find closest pair of points in points[lo..hi]
// precondition: points[lo..hi] and pointsByY[lo..hi] are the same sequence of points
// precondition: points[lo..hi] sorted by x-coordinate
// postcondition: pointsByY[lo..hi] sorted by y-coordinate
private int closest(MyPoint[] pointsByX, MyPoint[] pointsByY, MyPoint[] aux, int lo, int hi) {
if (hi <= lo) return Integer.MAX_VALUE;
int mid = lo + (hi - lo) / 2;
MyPoint median = pointsByX[mid];
// compute closest pair with both endpoints in left subarray or both in right subarray
int delta1 = closest(pointsByX, pointsByY, aux, lo, mid);
int delta2 = closest(pointsByX, pointsByY, aux, mid+1, hi);
int delta = Math.min(delta1, delta2);
// merge back so that pointsByY[lo..hi] are sorted by y-coordinate
merge(pointsByY, aux, lo, mid, hi);
// aux[0..m-1] = sequence of points closer than delta, sorted by y-coordinate
int m = 0;
for (int i = lo; i <= hi; i++) {
if (distanceTo(pointsByY[i], median) < delta)
aux[m++] = pointsByY[i];
}
// compare each point to its neighbors with y-coordinate closer than delta
for (int i = 0; i < m; i++) {
// a geometric packing argument shows that this loop iterates at most 7 times
for (int j = i+1; (j < m) && (distanceTo(aux[j], aux[i]) < delta); j++) {
int distance = distanceTo(aux[i], aux[j]);
if (distance < delta) {
delta = distance;
if (distance < bestDistance) {
bestDistance = delta;
best1 = aux[i];
best2 = aux[j];
}
}
}
}
return delta;
}
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
public MyPoint either() {
return best1;
}
public MyPoint other() {
return best2;
}
public double distance() {
return bestDistance;
}
public int distanceTo(MyPoint p1, MyPoint p2){
return Math.max(Math.abs(p1.x - p2.x)/2, Math.abs(p1.y - p2.y)/2) ;
//return Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2) ;
}
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public int bruteForce(List<MyPoint> points) {
Point p1 = null ;
Point p2 = null ;
double distanceResult = Double.MAX_VALUE ;
int numPoints = points.size();
if (numPoints < 2)
return 0;
if (numPoints >= 2) {
for (int i = 0; i < numPoints - 1; i++) {
MyPoint point1 = points.get(i);
for (int j = i + 1; j < numPoints; j++) {
MyPoint point2 = points.get(j);
double distance = this.distanceTo(point1, point2);
if (distance < distanceResult){
distanceResult = distance ;
p1 = point1 ;
p2 = point2 ;
}
}
}
}
//System.out.println("brute points found " + p1 + " " + p2);
return Math.max(Math.abs(p1.x - p2.x)/2, Math.abs(p1.y - p2.y)/2) ;
}
public int finalCheck(MyPoint[] points, MyPoint p1 , MyPoint p2, int delta){
for (int i = 0; i < points.length; i++) {
if (!points[i].equals(p1) && distanceTo(points[i], p1) < delta){
return distanceTo(points[i], p1) ;
}
if (!points[i].equals(p2) && distanceTo(points[i], p2) < delta){
return distanceTo(points[i], p2) ;
}
}
return delta ;
}
}
public class Sheeps {
public int solution(int[] X, int[]Y){
MyPoint[] points = new MyPoint[X.length] ;
for(int i = 0 ; i < X.length ; i++){
points[i] = new MyPoint(X[i], Y[i]) ;
}
ClosestPairCustom cp = new ClosestPairCustom(points) ;
//System.out.println("cp points found " + cp.other() + " " + cp.either());
int D = Math.max(Math.abs(cp.either().x - cp.other().x)/2, Math.abs(cp.either().y - cp.other().y)/2) ;
D = Math.min(cp.finalCheck(points, cp.either(), cp.other(), D), D);
return D;
}
public int solutionBrute(int[] X, int[]Y){
List<MyPoint> pointsList = new ArrayList<MyPoint>() ;
MyPoint[] points = new MyPoint[X.length] ;
for(int i = 0 ; i < X.length ; i++){
points[i] = new MyPoint(X[i], Y[i]) ;
pointsList.add(new MyPoint(X[i], Y[i])) ;
}
ClosestPairCustom cp = new ClosestPairCustom(points) ;
return cp.bruteForce(pointsList) ;
}
}
Code: 22:16:36 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225
package codility.rubidium;
import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
// implement point comparable by x ... w function distance to ...
class MyPoint extends Point implements Comparable<MyPoint> {
public MyPoint(int x, int y){
this.x = x ;
this.y = y ;
}
@Override
public String toString(){
return "x:"+this.x + ",y:" +this.y ;
}
@Override
public int compareTo(MyPoint o) {
if(this.x == o.x){
return this.y - o.y ;
}
return this.x - o.x ;
}
}
class ClosestPairCustom {
// closest pair of points and their Euclidean distance
private MyPoint best1, best2;
private MyPoint nearestToBest1, nearestToBest2;
private int bestDistance = Integer.MAX_VALUE;
double point1Distance = Double.MAX_VALUE;
double point2Distance = Double.MAX_VALUE;
public ClosestPairCustom(MyPoint[] points) {
int n = points.length;
if (n <= 1) return;
// sort by x-coordinate (breaking ties by y-coordinate)
Arrays.sort(points);
// check for co-incident points
for (int i = 0; i < n-1; i++) {
if (points[i].equals(points[i+1])) {
bestDistance = 0;
best1 = points[i];
best2 = points[i+1];
return;
}
}
// sort by y-coordinate (but not yet sorted)
MyPoint[] pointsByY = new MyPoint[n];
for (int i = 0; i < n; i++)
pointsByY[i] = points[i];
// auxiliary array
MyPoint[] aux = new MyPoint[n];
closest(points, pointsByY, aux, 0, n-1);
}
// find closest pair of points in points[lo..hi]
// precondition: points[lo..hi] and pointsByY[lo..hi] are the same sequence of points
// precondition: points[lo..hi] sorted by x-coordinate
// postcondition: pointsByY[lo..hi] sorted by y-coordinate
private int closest(MyPoint[] pointsByX, MyPoint[] pointsByY, MyPoint[] aux, int lo, int hi) {
if (hi <= lo) return Integer.MAX_VALUE;
int mid = lo + (hi - lo) / 2;
MyPoint median = pointsByX[mid];
// compute closest pair with both endpoints in left subarray or both in right subarray
int delta1 = closest(pointsByX, pointsByY, aux, lo, mid);
int delta2 = closest(pointsByX, pointsByY, aux, mid+1, hi);
int delta = Math.min(delta1, delta2);
// merge back so that pointsByY[lo..hi] are sorted by y-coordinate
merge(pointsByY, aux, lo, mid, hi);
// aux[0..m-1] = sequence of points closer than delta, sorted by y-coordinate
int m = 0;
for (int i = lo; i <= hi; i++) {
if (distanceTo(pointsByY[i], median) < delta)
aux[m++] = pointsByY[i];
}
// compare each point to its neighbors with y-coordinate closer than delta
for (int i = 0; i < m; i++) {
// a geometric packing argument shows that this loop iterates at most 7 times
for (int j = i+1; (j < m) && (distanceTo(aux[j], aux[i]) < delta); j++) {
int distance = distanceTo(aux[i], aux[j]);
if (distance < delta) {
delta = distance;
if (distance < bestDistance) {
bestDistance = delta;
best1 = aux[i];
best2 = aux[j];
}
}
}
}
return delta;
}
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
public MyPoint either() {
return best1;
}
public MyPoint other() {
return best2;
}
public double distance() {
return bestDistance;
}
public int distanceTo(MyPoint p1, MyPoint p2){
return Math.max(Math.abs(p1.x - p2.x)/2, Math.abs(p1.y - p2.y)/2) ;
//return Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2) ;
}
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public int bruteForce(List<MyPoint> points) {
Point p1 = null ;
Point p2 = null ;
double distanceResult = Double.MAX_VALUE ;
int numPoints = points.size();
if (numPoints < 2)
return 0;
if (numPoints >= 2) {
for (int i = 0; i < numPoints - 1; i++) {
MyPoint point1 = points.get(i);
for (int j = i + 1; j < numPoints; j++) {
MyPoint point2 = points.get(j);
double distance = this.distanceTo(point1, point2);
if (distance < distanceResult){
distanceResult = distance ;
p1 = point1 ;
p2 = point2 ;
}
}
}
}
//System.out.println("brute points found " + p1 + " " + p2);
return Math.max(Math.abs(p1.x - p2.x)/2, Math.abs(p1.y - p2.y)/2) ;
}
public int finalCheck(MyPoint[] points, MyPoint p1 , MyPoint p2, int delta){
for (int i = 0; i < points.length; i++) {
if (!points[i].equals(p1) && distanceTo(points[i], p1) < delta){
return distanceTo(points[i], p1) ;
}
if (!points[i].equals(p2) && distanceTo(points[i], p2) < delta){
return distanceTo(points[i], p2) ;
}
}
return delta ;
}
}
public class Solution {
public int solution(int[] X, int[]Y){
MyPoint[] points = new MyPoint[X.length] ;
for(int i = 0 ; i < X.length ; i++){
points[i] = new MyPoint(X[i], Y[i]) ;
}
ClosestPairCustom cp = new ClosestPairCustom(points) ;
//System.out.println("cp points found " + cp.other() + " " + cp.either());
int D = Math.max(Math.abs(cp.either().x - cp.other().x)/2, Math.abs(cp.either().y - cp.other().y)/2) ;
D = Math.min(cp.finalCheck(points, cp.either(), cp.other(), D), D);
return D;
}
public int solutionBrute(int[] X, int[]Y){
List<MyPoint> pointsList = new ArrayList<MyPoint>() ;
MyPoint[] points = new MyPoint[X.length] ;
for(int i = 0 ; i < X.length ; i++){
points[i] = new MyPoint(X[i], Y[i]) ;
pointsList.add(new MyPoint(X[i], Y[i])) ;
}
ClosestPairCustom cp = new ClosestPairCustom(points) ;
return cp.bruteForce(pointsList) ;
}
}
Code: 22:16:39 UTC,
java,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225
package codility.rubidium;
import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
// implement point comparable by x ... w function distance to ...
class MyPoint extends Point implements Comparable<MyPoint> {
public MyPoint(int x, int y){
this.x = x ;
this.y = y ;
}
@Override
public String toString(){
return "x:"+this.x + ",y:" +this.y ;
}
@Override
public int compareTo(MyPoint o) {
if(this.x == o.x){
return this.y - o.y ;
}
return this.x - o.x ;
}
}
class ClosestPairCustom {
// closest pair of points and their Euclidean distance
private MyPoint best1, best2;
private MyPoint nearestToBest1, nearestToBest2;
private int bestDistance = Integer.MAX_VALUE;
double point1Distance = Double.MAX_VALUE;
double point2Distance = Double.MAX_VALUE;
public ClosestPairCustom(MyPoint[] points) {
int n = points.length;
if (n <= 1) return;
// sort by x-coordinate (breaking ties by y-coordinate)
Arrays.sort(points);
// check for co-incident points
for (int i = 0; i < n-1; i++) {
if (points[i].equals(points[i+1])) {
bestDistance = 0;
best1 = points[i];
best2 = points[i+1];
return;
}
}
// sort by y-coordinate (but not yet sorted)
MyPoint[] pointsByY = new MyPoint[n];
for (int i = 0; i < n; i++)
pointsByY[i] = points[i];
// auxiliary array
MyPoint[] aux = new MyPoint[n];
closest(points, pointsByY, aux, 0, n-1);
}
// find closest pair of points in points[lo..hi]
// precondition: points[lo..hi] and pointsByY[lo..hi] are the same sequence of points
// precondition: points[lo..hi] sorted by x-coordinate
// postcondition: pointsByY[lo..hi] sorted by y-coordinate
private int closest(MyPoint[] pointsByX, MyPoint[] pointsByY, MyPoint[] aux, int lo, int hi) {
if (hi <= lo) return Integer.MAX_VALUE;
int mid = lo + (hi - lo) / 2;
MyPoint median = pointsByX[mid];
// compute closest pair with both endpoints in left subarray or both in right subarray
int delta1 = closest(pointsByX, pointsByY, aux, lo, mid);
int delta2 = closest(pointsByX, pointsByY, aux, mid+1, hi);
int delta = Math.min(delta1, delta2);
// merge back so that pointsByY[lo..hi] are sorted by y-coordinate
merge(pointsByY, aux, lo, mid, hi);
// aux[0..m-1] = sequence of points closer than delta, sorted by y-coordinate
int m = 0;
for (int i = lo; i <= hi; i++) {
if (distanceTo(pointsByY[i], median) < delta)
aux[m++] = pointsByY[i];
}
// compare each point to its neighbors with y-coordinate closer than delta
for (int i = 0; i < m; i++) {
// a geometric packing argument shows that this loop iterates at most 7 times
for (int j = i+1; (j < m) && (distanceTo(aux[j], aux[i]) < delta); j++) {
int distance = distanceTo(aux[i], aux[j]);
if (distance < delta) {
delta = distance;
if (distance < bestDistance) {
bestDistance = delta;
best1 = aux[i];
best2 = aux[j];
}
}
}
}
return delta;
}
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
public MyPoint either() {
return best1;
}
public MyPoint other() {
return best2;
}
public double distance() {
return bestDistance;
}
public int distanceTo(MyPoint p1, MyPoint p2){
return Math.max(Math.abs(p1.x - p2.x)/2, Math.abs(p1.y - p2.y)/2) ;
//return Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2) ;
}
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public int bruteForce(List<MyPoint> points) {
Point p1 = null ;
Point p2 = null ;
double distanceResult = Double.MAX_VALUE ;
int numPoints = points.size();
if (numPoints < 2)
return 0;
if (numPoints >= 2) {
for (int i = 0; i < numPoints - 1; i++) {
MyPoint point1 = points.get(i);
for (int j = i + 1; j < numPoints; j++) {
MyPoint point2 = points.get(j);
double distance = this.distanceTo(point1, point2);
if (distance < distanceResult){
distanceResult = distance ;
p1 = point1 ;
p2 = point2 ;
}
}
}
}
//System.out.println("brute points found " + p1 + " " + p2);
return Math.max(Math.abs(p1.x - p2.x)/2, Math.abs(p1.y - p2.y)/2) ;
}
public int finalCheck(MyPoint[] points, MyPoint p1 , MyPoint p2, int delta){
for (int i = 0; i < points.length; i++) {
if (!points[i].equals(p1) && distanceTo(points[i], p1) < delta){
return distanceTo(points[i], p1) ;
}
if (!points[i].equals(p2) && distanceTo(points[i], p2) < delta){
return distanceTo(points[i], p2) ;
}
}
return delta ;
}
}
public class Solution {
public int solution(int[] X, int[]Y){
MyPoint[] points = new MyPoint[X.length] ;
for(int i = 0 ; i < X.length ; i++){
points[i] = new MyPoint(X[i], Y[i]) ;
}
ClosestPairCustom cp = new ClosestPairCustom(points) ;
//System.out.println("cp points found " + cp.other() + " " + cp.either());
int D = Math.max(Math.abs(cp.either().x - cp.other().x)/2, Math.abs(cp.either().y - cp.other().y)/2) ;
D = Math.min(cp.finalCheck(points, cp.either(), cp.other(), D), D);
return D;
}
public int solutionBrute(int[] X, int[]Y){
List<MyPoint> pointsList = new ArrayList<MyPoint>() ;
MyPoint[] points = new MyPoint[X.length] ;
for(int i = 0 ; i < X.length ; i++){
points[i] = new MyPoint(X[i], Y[i]) ;
pointsList.add(new MyPoint(X[i], Y[i])) ;
}
ClosestPairCustom cp = new ClosestPairCustom(points) ;
return cp.bruteForce(pointsList) ;
}
}
Analysis
Compile error
./Solution.java:11: error: duplicate class: codility.rubidium.MyPoint
class MyPoint extends Point implements Comparable<MyPoint> {
^
./Solution.java:33: error: duplicate class: codility.rubidium.ClosestPairCustom
class ClosestPairCustom {
^
./Solution.java:197: error: duplicate class: codility.rubidium.Solution
public class Solution {
^
exec.java:16: error: cannot access Solution
Solution sol;
^
bad source file: ./Solution.java
file does not contain class Solution
Please remove or make sure it appears in the correct subdirectory of the sourcepath.
Code: 22:16:47 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224
package codility.rubidium;
import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
// implement point comparable by x ... w function distance to ...
class MyPoint extends Point implements Comparable<MyPoint> {
public MyPoint(int x, int y){
this.x = x ;
this.y = y ;
}
@Override
public String toString(){
return "x:"+this.x + ",y:" +this.y ;
}
@Override
public int compareTo(MyPoint o) {
if(this.x == o.x){
return this.y - o.y ;
}
return this.x - o.x ;
}
}
class ClosestPairCustom {
// closest pair of points and their Euclidean distance
private MyPoint best1, best2;
private MyPoint nearestToBest1, nearestToBest2;
private int bestDistance = Integer.MAX_VALUE;
double point1Distance = Double.MAX_VALUE;
double point2Distance = Double.MAX_VALUE;
public ClosestPairCustom(MyPoint[] points) {
int n = points.length;
if (n <= 1) return;
// sort by x-coordinate (breaking ties by y-coordinate)
Arrays.sort(points);
// check for co-incident points
for (int i = 0; i < n-1; i++) {
if (points[i].equals(points[i+1])) {
bestDistance = 0;
best1 = points[i];
best2 = points[i+1];
return;
}
}
// sort by y-coordinate (but not yet sorted)
MyPoint[] pointsByY = new MyPoint[n];
for (int i = 0; i < n; i++)
pointsByY[i] = points[i];
// auxiliary array
MyPoint[] aux = new MyPoint[n];
closest(points, pointsByY, aux, 0, n-1);
}
// find closest pair of points in points[lo..hi]
// precondition: points[lo..hi] and pointsByY[lo..hi] are the same sequence of points
// precondition: points[lo..hi] sorted by x-coordinate
// postcondition: pointsByY[lo..hi] sorted by y-coordinate
private int closest(MyPoint[] pointsByX, MyPoint[] pointsByY, MyPoint[] aux, int lo, int hi) {
if (hi <= lo) return Integer.MAX_VALUE;
int mid = lo + (hi - lo) / 2;
MyPoint median = pointsByX[mid];
// compute closest pair with both endpoints in left subarray or both in right subarray
int delta1 = closest(pointsByX, pointsByY, aux, lo, mid);
int delta2 = closest(pointsByX, pointsByY, aux, mid+1, hi);
int delta = Math.min(delta1, delta2);
// merge back so that pointsByY[lo..hi] are sorted by y-coordinate
merge(pointsByY, aux, lo, mid, hi);
// aux[0..m-1] = sequence of points closer than delta, sorted by y-coordinate
int m = 0;
for (int i = lo; i <= hi; i++) {
if (distanceTo(pointsByY[i], median) < delta)
aux[m++] = pointsByY[i];
}
// compare each point to its neighbors with y-coordinate closer than delta
for (int i = 0; i < m; i++) {
// a geometric packing argument shows that this loop iterates at most 7 times
for (int j = i+1; (j < m) && (distanceTo(aux[j], aux[i]) < delta); j++) {
int distance = distanceTo(aux[i], aux[j]);
if (distance < delta) {
delta = distance;
if (distance < bestDistance) {
bestDistance = delta;
best1 = aux[i];
best2 = aux[j];
}
}
}
}
return delta;
}
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
public MyPoint either() {
return best1;
}
public MyPoint other() {
return best2;
}
public double distance() {
return bestDistance;
}
public int distanceTo(MyPoint p1, MyPoint p2){
return Math.max(Math.abs(p1.x - p2.x)/2, Math.abs(p1.y - p2.y)/2) ;
//return Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2) ;
}
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public int bruteForce(List<MyPoint> points) {
Point p1 = null ;
Point p2 = null ;
double distanceResult = Double.MAX_VALUE ;
int numPoints = points.size();
if (numPoints < 2)
return 0;
if (numPoints >= 2) {
for (int i = 0; i < numPoints - 1; i++) {
MyPoint point1 = points.get(i);
for (int j = i + 1; j < numPoints; j++) {
MyPoint point2 = points.get(j);
double distance = this.distanceTo(point1, point2);
if (distance < distanceResult){
distanceResult = distance ;
p1 = point1 ;
p2 = point2 ;
}
}
}
}
//System.out.println("brute points found " + p1 + " " + p2);
return Math.max(Math.abs(p1.x - p2.x)/2, Math.abs(p1.y - p2.y)/2) ;
}
public int finalCheck(MyPoint[] points, MyPoint p1 , MyPoint p2, int delta){
for (int i = 0; i < points.length; i++) {
if (!points[i].equals(p1) && distanceTo(points[i], p1) < delta){
return distanceTo(points[i], p1) ;
}
if (!points[i].equals(p2) && distanceTo(points[i], p2) < delta){
return distanceTo(points[i], p2) ;
}
}
return delta ;
}
}
public class Solution {
public int solution(int[] X, int[]Y){
MyPoint[] points = new MyPoint[X.length] ;
for(int i = 0 ; i < X.length ; i++){
points[i] = new MyPoint(X[i], Y[i]) ;
}
ClosestPairCustom cp = new ClosestPairCustom(points) ;
int D = Math.max(Math.abs(cp.either().x - cp.other().x)/2, Math.abs(cp.either().y - cp.other().y)/2) ;
D = Math.min(cp.finalCheck(points, cp.either(), cp.other(), D), D);
return D;
}
public int solutionBrute(int[] X, int[]Y){
List<MyPoint> pointsList = new ArrayList<MyPoint>() ;
MyPoint[] points = new MyPoint[X.length] ;
for(int i = 0 ; i < X.length ; i++){
points[i] = new MyPoint(X[i], Y[i]) ;
pointsList.add(new MyPoint(X[i], Y[i])) ;
}
ClosestPairCustom cp = new ClosestPairCustom(points) ;
return cp.bruteForce(pointsList) ;
}
}
Code: 22:16:50 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222
import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
// implement point comparable by x ... w function distance to ...
class MyPoint extends Point implements Comparable<MyPoint> {
public MyPoint(int x, int y){
this.x = x ;
this.y = y ;
}
@Override
public String toString(){
return "x:"+this.x + ",y:" +this.y ;
}
@Override
public int compareTo(MyPoint o) {
if(this.x == o.x){
return this.y - o.y ;
}
return this.x - o.x ;
}
}
class ClosestPairCustom {
// closest pair of points and their Euclidean distance
private MyPoint best1, best2;
private MyPoint nearestToBest1, nearestToBest2;
private int bestDistance = Integer.MAX_VALUE;
double point1Distance = Double.MAX_VALUE;
double point2Distance = Double.MAX_VALUE;
public ClosestPairCustom(MyPoint[] points) {
int n = points.length;
if (n <= 1) return;
// sort by x-coordinate (breaking ties by y-coordinate)
Arrays.sort(points);
// check for co-incident points
for (int i = 0; i < n-1; i++) {
if (points[i].equals(points[i+1])) {
bestDistance = 0;
best1 = points[i];
best2 = points[i+1];
return;
}
}
// sort by y-coordinate (but not yet sorted)
MyPoint[] pointsByY = new MyPoint[n];
for (int i = 0; i < n; i++)
pointsByY[i] = points[i];
// auxiliary array
MyPoint[] aux = new MyPoint[n];
closest(points, pointsByY, aux, 0, n-1);
}
// find closest pair of points in points[lo..hi]
// precondition: points[lo..hi] and pointsByY[lo..hi] are the same sequence of points
// precondition: points[lo..hi] sorted by x-coordinate
// postcondition: pointsByY[lo..hi] sorted by y-coordinate
private int closest(MyPoint[] pointsByX, MyPoint[] pointsByY, MyPoint[] aux, int lo, int hi) {
if (hi <= lo) return Integer.MAX_VALUE;
int mid = lo + (hi - lo) / 2;
MyPoint median = pointsByX[mid];
// compute closest pair with both endpoints in left subarray or both in right subarray
int delta1 = closest(pointsByX, pointsByY, aux, lo, mid);
int delta2 = closest(pointsByX, pointsByY, aux, mid+1, hi);
int delta = Math.min(delta1, delta2);
// merge back so that pointsByY[lo..hi] are sorted by y-coordinate
merge(pointsByY, aux, lo, mid, hi);
// aux[0..m-1] = sequence of points closer than delta, sorted by y-coordinate
int m = 0;
for (int i = lo; i <= hi; i++) {
if (distanceTo(pointsByY[i], median) < delta)
aux[m++] = pointsByY[i];
}
// compare each point to its neighbors with y-coordinate closer than delta
for (int i = 0; i < m; i++) {
// a geometric packing argument shows that this loop iterates at most 7 times
for (int j = i+1; (j < m) && (distanceTo(aux[j], aux[i]) < delta); j++) {
int distance = distanceTo(aux[i], aux[j]);
if (distance < delta) {
delta = distance;
if (distance < bestDistance) {
bestDistance = delta;
best1 = aux[i];
best2 = aux[j];
}
}
}
}
return delta;
}
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
public MyPoint either() {
return best1;
}
public MyPoint other() {
return best2;
}
public double distance() {
return bestDistance;
}
public int distanceTo(MyPoint p1, MyPoint p2){
return Math.max(Math.abs(p1.x - p2.x)/2, Math.abs(p1.y - p2.y)/2) ;
//return Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2) ;
}
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public int bruteForce(List<MyPoint> points) {
Point p1 = null ;
Point p2 = null ;
double distanceResult = Double.MAX_VALUE ;
int numPoints = points.size();
if (numPoints < 2)
return 0;
if (numPoints >= 2) {
for (int i = 0; i < numPoints - 1; i++) {
MyPoint point1 = points.get(i);
for (int j = i + 1; j < numPoints; j++) {
MyPoint point2 = points.get(j);
double distance = this.distanceTo(point1, point2);
if (distance < distanceResult){
distanceResult = distance ;
p1 = point1 ;
p2 = point2 ;
}
}
}
}
//System.out.println("brute points found " + p1 + " " + p2);
return Math.max(Math.abs(p1.x - p2.x)/2, Math.abs(p1.y - p2.y)/2) ;
}
public int finalCheck(MyPoint[] points, MyPoint p1 , MyPoint p2, int delta){
for (int i = 0; i < points.length; i++) {
if (!points[i].equals(p1) && distanceTo(points[i], p1) < delta){
return distanceTo(points[i], p1) ;
}
if (!points[i].equals(p2) && distanceTo(points[i], p2) < delta){
return distanceTo(points[i], p2) ;
}
}
return delta ;
}
}
public class Solution {
public int solution(int[] X, int[]Y){
MyPoint[] points = new MyPoint[X.length] ;
for(int i = 0 ; i < X.length ; i++){
points[i] = new MyPoint(X[i], Y[i]) ;
}
ClosestPairCustom cp = new ClosestPairCustom(points) ;
int D = Math.max(Math.abs(cp.either().x - cp.other().x)/2, Math.abs(cp.either().y - cp.other().y)/2) ;
D = Math.min(cp.finalCheck(points, cp.either(), cp.other(), D), D);
return D;
}
public int solutionBrute(int[] X, int[]Y){
List<MyPoint> pointsList = new ArrayList<MyPoint>() ;
MyPoint[] points = new MyPoint[X.length] ;
for(int i = 0 ; i < X.length ; i++){
points[i] = new MyPoint(X[i], Y[i]) ;
pointsList.add(new MyPoint(X[i], Y[i])) ;
}
ClosestPairCustom cp = new ClosestPairCustom(points) ;
return cp.bruteForce(pointsList) ;
}
}
Analysis
Code: 22:16:55 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222
import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
// implement point comparable by x ... w function distance to ...
class MyPoint extends Point implements Comparable<MyPoint> {
public MyPoint(int x, int y){
this.x = x ;
this.y = y ;
}
@Override
public String toString(){
return "x:"+this.x + ",y:" +this.y ;
}
@Override
public int compareTo(MyPoint o) {
if(this.x == o.x){
return this.y - o.y ;
}
return this.x - o.x ;
}
}
class ClosestPairCustom {
// closest pair of points and their Euclidean distance
private MyPoint best1, best2;
private MyPoint nearestToBest1, nearestToBest2;
private int bestDistance = Integer.MAX_VALUE;
double point1Distance = Double.MAX_VALUE;
double point2Distance = Double.MAX_VALUE;
public ClosestPairCustom(MyPoint[] points) {
int n = points.length;
if (n <= 1) return;
// sort by x-coordinate (breaking ties by y-coordinate)
Arrays.sort(points);
// check for co-incident points
for (int i = 0; i < n-1; i++) {
if (points[i].equals(points[i+1])) {
bestDistance = 0;
best1 = points[i];
best2 = points[i+1];
return;
}
}
// sort by y-coordinate (but not yet sorted)
MyPoint[] pointsByY = new MyPoint[n];
for (int i = 0; i < n; i++)
pointsByY[i] = points[i];
// auxiliary array
MyPoint[] aux = new MyPoint[n];
closest(points, pointsByY, aux, 0, n-1);
}
// find closest pair of points in points[lo..hi]
// precondition: points[lo..hi] and pointsByY[lo..hi] are the same sequence of points
// precondition: points[lo..hi] sorted by x-coordinate
// postcondition: pointsByY[lo..hi] sorted by y-coordinate
private int closest(MyPoint[] pointsByX, MyPoint[] pointsByY, MyPoint[] aux, int lo, int hi) {
if (hi <= lo) return Integer.MAX_VALUE;
int mid = lo + (hi - lo) / 2;
MyPoint median = pointsByX[mid];
// compute closest pair with both endpoints in left subarray or both in right subarray
int delta1 = closest(pointsByX, pointsByY, aux, lo, mid);
int delta2 = closest(pointsByX, pointsByY, aux, mid+1, hi);
int delta = Math.min(delta1, delta2);
// merge back so that pointsByY[lo..hi] are sorted by y-coordinate
merge(pointsByY, aux, lo, mid, hi);
// aux[0..m-1] = sequence of points closer than delta, sorted by y-coordinate
int m = 0;
for (int i = lo; i <= hi; i++) {
if (distanceTo(pointsByY[i], median) < delta)
aux[m++] = pointsByY[i];
}
// compare each point to its neighbors with y-coordinate closer than delta
for (int i = 0; i < m; i++) {
// a geometric packing argument shows that this loop iterates at most 7 times
for (int j = i+1; (j < m) && (distanceTo(aux[j], aux[i]) < delta); j++) {
int distance = distanceTo(aux[i], aux[j]);
if (distance < delta) {
delta = distance;
if (distance < bestDistance) {
bestDistance = delta;
best1 = aux[i];
best2 = aux[j];
}
}
}
}
return delta;
}
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
public MyPoint either() {
return best1;
}
public MyPoint other() {
return best2;
}
public double distance() {
return bestDistance;
}
public int distanceTo(MyPoint p1, MyPoint p2){
return Math.max(Math.abs(p1.x - p2.x)/2, Math.abs(p1.y - p2.y)/2) ;
//return Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2) ;
}
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public int bruteForce(List<MyPoint> points) {
Point p1 = null ;
Point p2 = null ;
double distanceResult = Double.MAX_VALUE ;
int numPoints = points.size();
if (numPoints < 2)
return 0;
if (numPoints >= 2) {
for (int i = 0; i < numPoints - 1; i++) {
MyPoint point1 = points.get(i);
for (int j = i + 1; j < numPoints; j++) {
MyPoint point2 = points.get(j);
double distance = this.distanceTo(point1, point2);
if (distance < distanceResult){
distanceResult = distance ;
p1 = point1 ;
p2 = point2 ;
}
}
}
}
//System.out.println("brute points found " + p1 + " " + p2);
return Math.max(Math.abs(p1.x - p2.x)/2, Math.abs(p1.y - p2.y)/2) ;
}
public int finalCheck(MyPoint[] points, MyPoint p1 , MyPoint p2, int delta){
for (int i = 0; i < points.length; i++) {
if (!points[i].equals(p1) && distanceTo(points[i], p1) < delta){
return distanceTo(points[i], p1) ;
}
if (!points[i].equals(p2) && distanceTo(points[i], p2) < delta){
return distanceTo(points[i], p2) ;
}
}
return delta ;
}
}
public class Solution {
public int solution(int[] X, int[]Y){
MyPoint[] points = new MyPoint[X.length] ;
for(int i = 0 ; i < X.length ; i++){
points[i] = new MyPoint(X[i], Y[i]) ;
}
ClosestPairCustom cp = new ClosestPairCustom(points) ;
int D = Math.max(Math.abs(cp.either().x - cp.other().x)/2, Math.abs(cp.either().y - cp.other().y)/2) ;
D = Math.min(cp.finalCheck(points, cp.either(), cp.other(), D), D);
return D;
}
public int solutionBrute(int[] X, int[]Y){
List<MyPoint> pointsList = new ArrayList<MyPoint>() ;
MyPoint[] points = new MyPoint[X.length] ;
for(int i = 0 ; i < X.length ; i++){
points[i] = new MyPoint(X[i], Y[i]) ;
pointsList.add(new MyPoint(X[i], Y[i])) ;
}
ClosestPairCustom cp = new ClosestPairCustom(points) ;
return cp.bruteForce(pointsList) ;
}
}
Analysis
Code: 22:17:00 UTC,
java,
final,
score:
100
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222
import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
// implement point comparable by x ... w function distance to ...
class MyPoint extends Point implements Comparable<MyPoint> {
public MyPoint(int x, int y){
this.x = x ;
this.y = y ;
}
@Override
public String toString(){
return "x:"+this.x + ",y:" +this.y ;
}
@Override
public int compareTo(MyPoint o) {
if(this.x == o.x){
return this.y - o.y ;
}
return this.x - o.x ;
}
}
class ClosestPairCustom {
// closest pair of points and their Euclidean distance
private MyPoint best1, best2;
private MyPoint nearestToBest1, nearestToBest2;
private int bestDistance = Integer.MAX_VALUE;
double point1Distance = Double.MAX_VALUE;
double point2Distance = Double.MAX_VALUE;
public ClosestPairCustom(MyPoint[] points) {
int n = points.length;
if (n <= 1) return;
// sort by x-coordinate (breaking ties by y-coordinate)
Arrays.sort(points);
// check for co-incident points
for (int i = 0; i < n-1; i++) {
if (points[i].equals(points[i+1])) {
bestDistance = 0;
best1 = points[i];
best2 = points[i+1];
return;
}
}
// sort by y-coordinate (but not yet sorted)
MyPoint[] pointsByY = new MyPoint[n];
for (int i = 0; i < n; i++)
pointsByY[i] = points[i];
// auxiliary array
MyPoint[] aux = new MyPoint[n];
closest(points, pointsByY, aux, 0, n-1);
}
// find closest pair of points in points[lo..hi]
// precondition: points[lo..hi] and pointsByY[lo..hi] are the same sequence of points
// precondition: points[lo..hi] sorted by x-coordinate
// postcondition: pointsByY[lo..hi] sorted by y-coordinate
private int closest(MyPoint[] pointsByX, MyPoint[] pointsByY, MyPoint[] aux, int lo, int hi) {
if (hi <= lo) return Integer.MAX_VALUE;
int mid = lo + (hi - lo) / 2;
MyPoint median = pointsByX[mid];
// compute closest pair with both endpoints in left subarray or both in right subarray
int delta1 = closest(pointsByX, pointsByY, aux, lo, mid);
int delta2 = closest(pointsByX, pointsByY, aux, mid+1, hi);
int delta = Math.min(delta1, delta2);
// merge back so that pointsByY[lo..hi] are sorted by y-coordinate
merge(pointsByY, aux, lo, mid, hi);
// aux[0..m-1] = sequence of points closer than delta, sorted by y-coordinate
int m = 0;
for (int i = lo; i <= hi; i++) {
if (distanceTo(pointsByY[i], median) < delta)
aux[m++] = pointsByY[i];
}
// compare each point to its neighbors with y-coordinate closer than delta
for (int i = 0; i < m; i++) {
// a geometric packing argument shows that this loop iterates at most 7 times
for (int j = i+1; (j < m) && (distanceTo(aux[j], aux[i]) < delta); j++) {
int distance = distanceTo(aux[i], aux[j]);
if (distance < delta) {
delta = distance;
if (distance < bestDistance) {
bestDistance = delta;
best1 = aux[i];
best2 = aux[j];
}
}
}
}
return delta;
}
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
public MyPoint either() {
return best1;
}
public MyPoint other() {
return best2;
}
public double distance() {
return bestDistance;
}
public int distanceTo(MyPoint p1, MyPoint p2){
return Math.max(Math.abs(p1.x - p2.x)/2, Math.abs(p1.y - p2.y)/2) ;
//return Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2) ;
}
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public int bruteForce(List<MyPoint> points) {
Point p1 = null ;
Point p2 = null ;
double distanceResult = Double.MAX_VALUE ;
int numPoints = points.size();
if (numPoints < 2)
return 0;
if (numPoints >= 2) {
for (int i = 0; i < numPoints - 1; i++) {
MyPoint point1 = points.get(i);
for (int j = i + 1; j < numPoints; j++) {
MyPoint point2 = points.get(j);
double distance = this.distanceTo(point1, point2);
if (distance < distanceResult){
distanceResult = distance ;
p1 = point1 ;
p2 = point2 ;
}
}
}
}
//System.out.println("brute points found " + p1 + " " + p2);
return Math.max(Math.abs(p1.x - p2.x)/2, Math.abs(p1.y - p2.y)/2) ;
}
public int finalCheck(MyPoint[] points, MyPoint p1 , MyPoint p2, int delta){
for (int i = 0; i < points.length; i++) {
if (!points[i].equals(p1) && distanceTo(points[i], p1) < delta){
return distanceTo(points[i], p1) ;
}
if (!points[i].equals(p2) && distanceTo(points[i], p2) < delta){
return distanceTo(points[i], p2) ;
}
}
return delta ;
}
}
public class Solution {
public int solution(int[] X, int[]Y){
MyPoint[] points = new MyPoint[X.length] ;
for(int i = 0 ; i < X.length ; i++){
points[i] = new MyPoint(X[i], Y[i]) ;
}
ClosestPairCustom cp = new ClosestPairCustom(points) ;
int D = Math.max(Math.abs(cp.either().x - cp.other().x)/2, Math.abs(cp.either().y - cp.other().y)/2) ;
D = Math.min(cp.finalCheck(points, cp.either(), cp.other(), D), D);
return D;
}
public int solutionBrute(int[] X, int[]Y){
List<MyPoint> pointsList = new ArrayList<MyPoint>() ;
MyPoint[] points = new MyPoint[X.length] ;
for(int i = 0 ; i < X.length ; i++){
points[i] = new MyPoint(X[i], Y[i]) ;
pointsList.add(new MyPoint(X[i], Y[i])) ;
}
ClosestPairCustom cp = new ClosestPairCustom(points) ;
return cp.bruteForce(pointsList) ;
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N*log(N))
expand all
Correctness tests
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
1.
0.008 s
OK
expand all
Performance tests
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.004 s
OK
5.
0.008 s
OK
1.
1.860 s
OK
1.
0.888 s
OK
2.
0.344 s
OK
1.
0.020 s
OK
2.
1.540 s
OK
1.
0.820 s
OK
2.
0.192 s
OK
3.
0.048 s
OK
1.
1.632 s
OK