1.

package acm_10245_the_closest_pair_problem;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: acm_10245_the_closest_pair_problem
* Link:
*
* @author Martin Lambeck
* @version 1.0, 28.10.2010
*
* Method : closest pair algorithm
* Status : Accepted
* Runtime: 1.856
*
* http://en.wikipedia.org/wiki/Closest_pair_of_points_problem#Planar_case
*/


public class Main
{
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in), 1024*32);

static double best;
static Point[] p = new Point[50001];


final static double INFINITY = 10000;

public static void main(String... args) throws IOException
{
for (int i = 0; i < p.length; i++)
p[i] = new Point();

while (testcase());
}

public static boolean testcase() throws IOException
{
int n = Integer.parseInt(in.readLine());

if (n == 0)
return false;

best = INFINITY;

for (int i = 0; i < n; i++)
{
String[] line = in.readLine().split(" ");

p[i].x = Double.parseDouble(line[0]);
p[i].y = Double.parseDouble(line[1]);
}


Arrays.sort(p, 0, n);


work(0, n-1);

if (best < INFINITY)
System.out.printf("%.4f%n", best);
else
System.out.println("INFINITY");

return true;
}

static void work(int from, int to)
{
if (to-from <= 1)
{
if ((to-from == 1) && (p[from].dist(p[to]) < best))
best = p[from].dist(p[to]);

return;
}


int mid = (to+from) / 2;


work(from, mid-1);
work(mid, to);

double rx = p[mid-1].x; //rightmost point in left subset
double lx = p[mid].x; //leftmost point in right subset

int maxHigh = -1; //rightmost point in right subset
//to be considered for a better solution

for (int i = mid; i <= to; i++)
{
if ((p[i].x - rx) >= best)
break;

maxHigh = i;
}

for (int i = mid-1; i >= 0; i--)
{
if ((lx - p[i].x) >= best)
break;

for (int j = mid; j <= maxHigh; j++)
{
double dist = p[i].dist(p[j]);

if (dist < best)
best = dist;
}
}
}
}

class Point implements Comparable<Point>
{
double x;
double y;

public int compareTo(Point o)
{
if (x == o.x)
return 0;

return (x < o.x ? -1 : 1);
}

public double dist (Point o)
{
return Math.hypot(x - o.x, y - o.y);
}
}



2.

 

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
 * Problem: 10245 - The Closest Pair Problem
* Link: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1186
*
 * @author Siegfried Ippisch
* @version 1.0
*
 * Method : Divide and Conquer
* Status : Accepted
* Runtime: 1.964
*/

import java.io.*;
import java.util.Arrays;

public class TheClosestPairProblem {
     
      public static class Point implements Comparable<Point>{
            public final double x, y;
           
            public Point(double x, double y){
                  this.x = x; this.y = y;
            }
           
            public double distance(Point other){
                  double dx = this.x - other.x;
                  double dy = this.y - other.y;
                  return Math.sqrt(dx*dx+dy*dy);
            }
           
            public int compareTo(Point other){
                  if(this.x < other.x)
                        return -1;
                  if(this.x > other.x)
                        return 1;
                  return 0;
            }
           
            public String toString(){
                  return "("+x+"|"+y+")";
            }
      }
     
      public static void main(String[] args) throws IOException{
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
           
            int n = Integer.parseInt(in.readLine());
            while(n != 0){
                  minDistance = Double.POSITIVE_INFINITY;
                  points = new Point[n];
                 
                  for(int i=0; i<n; i++){
                        String[] s = in.readLine().split(" ");
                        points[i] = new Point(Double.parseDouble(s[0]), Double.parseDouble(s[1]));
                  }
                 
                  Arrays.sort(points);
                 
                  minDistance(0,n);
                  if(minDistance >= 10000 || n==1)
                        System.out.println("INFINITY");
                  else
                        System.out.printf("%.4f%n",minDistance);
                 
                  n = Integer.parseInt(in.readLine());
            }
           
            in.close();
      }
     
      private static Point[] points = null;
      private static double minDistance = Double.POSITIVE_INFINITY;
     
      // Intervall [a,b[
      private static void minDistance(int a, int b) {
           
            if(b - a <= 1)
                  return;
           
            int m = (a+b)/2;
            minDistance(a,m);
            minDistance(m,b);
           
            for(int i=m-1; i>=a; i--){
                  if(points[i].x < points[m].x - minDistance) break;
                  for(int j=m; j<b; j++){
                        if(points[i].x < points[j].x - minDistance) break;
                        minDistance = Math.min(points[i].distance(points[j]),minDistance);
                  }
            }
      }
}

3.

/**
* ACM Training 2009
* ACM Problem #10245 - The Closest Pair Problem
*
* @author Felix Dietrich
* @version 1.0, 10/31/2009
*
* Methode: Closest Pair Algo
* Status : Accepted
* Runtime: 2.916
* http://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=1186&mosmsg=Submission+received+with+ID+7524024
*/

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

class Main
{
/**
* Standart point class
*/
public static class Point implements Comparable<Point>
{
protected double x;
protected double y;

public Point(double d, double e)
{
this.x = d;
this.y = e;
}

/**
* Compares two points by x and y value
*/
@Override
public int compareTo(Point p1)
{
if(Math.abs(this.x - p1.x) < 1e-6)
{
if(Math.abs(this.y - p1.y) < 1e-6)
return 0;
if(this.y < p1.y)
return -1;
else
return 1;
}
if(this.x < p1.x)
return -1;
else
return 1;
}
}

public static void main(String... as) throws IOException
{
Scanner sc;
sc = new Scanner(System.in);

int n;
List<Point> points = new ArrayList<Point>();
List<Point> newpoints = new ArrayList<Point>();
Point q,r;
double distance;

while(sc.hasNext())
{
points.clear();
newpoints.clear();

n = sc.nextInt();
if(n == 0)
return;

// Read the points
for(int i=0; i<n; i++)
points.add(new Point(sc.nextDouble(), sc.nextDouble()));

if(points.size() == 1)
{
System.out.println("INFINITY");
continue;
}

// sort ascending by x and y value
Collections.sort( points );

q = points.get(0);
r = points.get(1);
newpoints.add(q);
newpoints.add(r);

distance = (q.x-r.x)*(q.x-r.x) + (q.y-r.y)*(q.y-r.y);

Point m;
Point pi;

for(int i=2; i<n; i++)
{
pi = points.get(i);
for(int k=0; k<newpoints.size(); k++)
{
m = newpoints.get(k);
if((pi.x - m.x)*(pi.x - m.x) > distance)
{
newpoints.remove(k);
k--;
}
else
if((pi.x-m.x)*(pi.x-m.x) + (pi.y-m.y)*(pi.y-m.y) < distance)
{
q = m;
r = pi;
distance = (pi.x-m.x)*(pi.x-m.x) + (pi.y-m.y)*(pi.y-m.y);
}
}
newpoints.add(pi);
}

distance = Math.hypot(q.x-r.x, q.y-r.y);
if(distance > 10000.0000 || Math.abs(distance - 10000.0000) < 1e-6)
System.out.println("INFINITY");
else
System.out.println(String.format("%.04f", distance));
}
}
}