fork(1) download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.ArrayList;
  5. import java.util.Comparator;
  6. import java.util.List;
  7. import java.util.StringTokenizer;
  8.  
  9. public class Main {
  10.     public static void main(String[] args) {
  11.         FastReader sc = new FastReader();
  12.  
  13.         Integer n = sc.nextInt();
  14.         if (n == null) return;
  15.  
  16.         List<Point> points = new ArrayList<>(n);
  17.         for (int i = 0; i < n; i++) {
  18.             int x = sc.nextInt();
  19.             int y = sc.nextInt();
  20.             points.add(new Point(i, x, y));
  21.         }
  22.  
  23.         PairResult result = closestPair(points);
  24.  
  25.         int index1 = Math.min(result.p1.index, result.p2.index);
  26.         int index2 = Math.max(result.p1.index, result.p2.index);
  27.  
  28.         System.out.printf("%d %d %.6f%n", index1, index2, result.dist);
  29.     }
  30.  
  31.     /*
  32.      This is the pre-processing sorting step explained in the lab report.
  33.      This method uses .sort method and looking and reading the method from
  34.      IntelliJ (if you use this IDE), it explained that this method implemented
  35.      Tim Sort, making the time complexity O(n log n) in the worst and average case
  36.      */
  37.  
  38.     public static PairResult closestPair(List<Point> points) {
  39.         int n = points.size();
  40.  
  41.         List<Point> pointsByX = new ArrayList<>(points);
  42.         List<Point> pointsByY = new ArrayList<>(points);
  43.  
  44.  
  45.         pointsByX.sort((p1, p2) -> {
  46.             if (p1.x != p2.x) return Double.compare(p1.x, p2.x);
  47.             if (p1.y != p2.y) return Double.compare(p1.y, p2.y);
  48.             return Integer.compare(p1.index, p2.index);
  49.         });
  50.  
  51.  
  52.         pointsByY.sort(Comparator.comparingDouble(p -> p.y));
  53.  
  54.         return closestPairRes(pointsByX, pointsByY);
  55.     }
  56.  
  57.  
  58.     private static PairResult closestPairRes(List<Point> pointsByX, List<Point> pointsByY) {
  59.  
  60.         int n = pointsByX.size();
  61.  
  62.         /*
  63.  
  64.         Simple base cases. If the length of points is only 2, return the two points and their distance.
  65.         If length of points is three, then do a brute force comparison.
  66.          */
  67.  
  68.         if (n == 2) {
  69.             return new PairResult(pointsByX.get(0), pointsByX.get(1), dist(pointsByX.get(0), pointsByX.get(1)));
  70.         }
  71.  
  72.         if (n == 3) {
  73.             Point p1 = pointsByX.get(0);
  74.             Point p2 = pointsByX.get(1);
  75.             Point p3 = pointsByX.get(2);
  76.  
  77.             double dist1 = dist(p1, p2);
  78.             double dist2 = dist(p2, p3);
  79.             double dist3 = dist(p3, p1);
  80.  
  81.             if (dist1 <= dist2 && dist1 <= dist3) {
  82.                 return new PairResult(p1, p2, dist1);
  83.             } else if (dist2 <= dist1 && dist2 <= dist3) {
  84.                 return new PairResult(p2, p3, dist2);
  85.             } else {
  86.                 return new PairResult(p1, p3, dist3);
  87.             }
  88.         }
  89.  
  90.  
  91.         int mid = n / 2;
  92.         Point midPoint = pointsByX.get(mid);
  93.  
  94.         List<Point> leftX = pointsByX.subList(0, mid);
  95.         List<Point> rightX = pointsByX.subList(mid, n);
  96.  
  97.         List<Point> leftY = new ArrayList<>(mid);
  98.         List<Point> rightY = new ArrayList<>(n - mid);
  99.  
  100.         /*
  101.             Putting the Y-sorted points into left and right sub arrays.
  102.             By iterating through the already sorted pointsByY list, we guaranteed
  103.             that leftY and rightY remain perfectly sorted by Y-coordinates.
  104.             This avoid another O(n log n) resort inside the recursive step
  105.             making this O(n log^2 n) and instead keeping this step strictly O(n)
  106.          */
  107.  
  108.         for (Point p : pointsByY) {
  109.             if (isLeftOf(p, midPoint)) {
  110.                 leftY.add(p);
  111.             } else {
  112.                 rightY.add(p);
  113.             }
  114.         }
  115.  
  116.         /*
  117.         This is the recursive step where closestPairRes() calls itself, the code below splits into
  118.         two sub problems of size n/2.
  119.          */
  120.  
  121.         PairResult dl = closestPairRes(leftX, leftY);
  122.         PairResult dr = closestPairRes(rightX, rightY);
  123.  
  124.         /*
  125.             delta (d) is the minimum distance strictly found on the left or the right.
  126.             Any pair of points spanning across the median line MUST have a distance
  127.             smaller than this d to be the true closest pair.
  128.         */
  129.  
  130.         PairResult closestPairResult = (dl.dist < dr.dist) ? dl : dr;
  131.         double d = closestPairResult.dist;
  132.  
  133.         List<Point> strip = new ArrayList<>();
  134.  
  135.         /*
  136.             Build the vertical strip centered at the median X-coordinate.
  137.             We only include points that are within a horizontal distance of d.
  138.  
  139.          */
  140.         for (Point p : pointsByY) {
  141.             if (Math.abs(p.x - midPoint.x) <= d) {
  142.                 strip.add(p);
  143.             }
  144.         }
  145.  
  146.         /*
  147.  
  148.         This strip is sorted by Y, the condition (strip.get(j).y - strip.get(i).y) < d
  149.         created a strict 2d x d bounding box above the candidate point. By the Pigeonhole
  150.         Principle, this region can hold a maximum of 8 points. That's why mathematically
  151.         the loop is guaranteed to fail the distance Y check and break after at most 7 comparison
  152.         keeping this step still O(n)
  153.  
  154.          */
  155.  
  156.         for (int i = 0; i < strip.size(); i++) {
  157.             for (int j = i + 1; j < strip.size() && (strip.get(j).y - strip.get(i).y) < d; j++) {
  158.                 double dist = dist(strip.get(i), strip.get(j));
  159.                 if (dist < d) {
  160.                     d = dist;
  161.                     closestPairResult = new PairResult(strip.get(i), strip.get(j), dist);
  162.                 }
  163.             }
  164.         }
  165.  
  166.         return closestPairResult;
  167.     }
  168.  
  169.     // Helper Methods / Classes
  170.  
  171.     public static boolean isLeftOf(Point p, Point midpoint) {
  172.         if (p.x != midpoint.x) return p.x < midpoint.x;
  173.         if (p.y != midpoint.y) return p.y < midpoint.y;
  174.         return p.index < midpoint.index;
  175.     }
  176.  
  177.     public static double dist(Point a, Point b) {
  178.         double dx = a.x - b.x;
  179.         double dy = a.y - b.y;
  180.         return Math.sqrt((dx * dx) + (dy * dy));
  181.     }
  182.  
  183.     private static class PairResult {
  184.         private final Point p1;
  185.         private final Point p2;
  186.         private final double dist;
  187.  
  188.         public PairResult(Point p1, Point p2, double dist) {
  189.             this.p1 = p1;
  190.             this.p2 = p2;
  191.             this.dist = dist;
  192.         }
  193.  
  194.     }
  195.  
  196.     private static class Point {
  197.         private final int index;
  198.         private double x, y;
  199.  
  200.         public Point(int index, double x, double y) {
  201.             this.index = index;
  202.             this.x = x;
  203.             this.y = y;
  204.         }
  205.     }
  206.  
  207.     // GeeksforGeeks FastReader Implementation
  208.     // Using this to hopefully get a accepted answer in SPOJ
  209.     // Since it's a competitive website and needs a efficient I/O
  210.     static class FastReader {
  211.         BufferedReader br;
  212.         StringTokenizer st;
  213.  
  214.         public FastReader() {
  215.             br = new BufferedReader(new InputStreamReader(System.in));
  216.         }
  217.  
  218.         String next() {
  219.             while (st == null || !st.hasMoreElements()) {
  220.                 try {
  221.                     String line = br.readLine();
  222.                     if (line == null || line.trim().isEmpty()) {
  223.                         return null; // Handle EOF safely
  224.                     }
  225.                     st = new StringTokenizer(line);
  226.                 } catch (IOException e) {
  227.                     e.printStackTrace();
  228.                     return null;
  229.                 }
  230.             }
  231.             return st.nextToken();
  232.         }
  233.  
  234.         Integer nextInt() {
  235.             String str = next();
  236.             if (str == null) return null;
  237.             return Integer.parseInt(str);
  238.         }
  239.     }
  240. }
Success #stdin #stdout 0.1s 54704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8QkLUB
problem CLOPPAIR, based on SPOJ submission 35990686 (JAVA), 2026-10-05 04:31:32
language:
Java (HotSpot 12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!