daily pastebin goal
18%
SHARE
TWEET

Pasty

a guest Dec 12th, 2018 54 in 143 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class Solution {
  5.  
  6.   public static String run(InputStream in) {
  7.     return new Solution().solve(in);
  8.   }
  9.  
  10.   public String solve(InputStream in) {
  11.     Scanner sc = new Scanner(in);
  12.     int n = sc.nextInt();
  13.     List<Point> points = new ArrayList<>();
  14.     for (int i = 0; i < n; i++) {
  15.       points.add(new Point(sc.nextDouble(), sc.nextDouble()));
  16.     }
  17.    
  18.     sc.close();
  19.     Util.sortByX(points);
  20.     return Double.toString(closestPair(points));
  21.   }
  22.  
  23.   /**
  24.    * Takes a list of points and returns the distance between the closest pair.
  25.    * This is done with divide and conquer.
  26.    *
  27.    * @param points
  28.    *     - list of points that need to be considered.
  29.    * @return smallest pair-wise distance between points.
  30.    */
  31.   public static double closestPair(List<Point> points) {
  32.     // TODO
  33.     if (points.size() <= 3) {
  34.       return Util.bruteForce(points);
  35.     }
  36.    
  37.     int mid = points.size() / 2;
  38.     List<Point> ptLeft = new ArrayList<>();
  39.     List<Point> ptRight = new ArrayList<>();
  40.    
  41.     int i = 0;
  42.     while (i < mid) {
  43.       ptLeft.add(points.get(i));
  44.       i++;
  45.     }
  46.     while (i < points.size()) {
  47.       ptRight.add(points.get(i));
  48.       i++;
  49.     }
  50.    
  51.     double dl = closestPair(ptLeft);
  52.     double dr = closestPair(ptRight);
  53.    
  54.     double d = Math.min(dl, dr);
  55.     i = 0;
  56.     List<Point> ptStrip = new ArrayList<>();
  57.     while (i < points.size()) {
  58.       if (Math.abs(points.get(mid).x - points.get(i).x) < d) {
  59.         ptStrip.add(points.get(i));
  60.       }
  61.         i++;
  62.     }
  63.     // return d;
  64.     return Math.min(d, closestStrip(ptStrip,d));
  65.   }
  66.  
  67.   public static double closestStrip(List<Point> points, double closest) {
  68.     Util.sortByY(points);
  69.     int size = points.size();
  70.     double bestDist = Double.POSITIVE_INFINITY;
  71.     for (int i = 0; i < size - 1; i++) {
  72.       Point point1 = points.get(i);
  73.       for (int j = i + 1; j < size; j++) {
  74.         Point point2 = points.get(j);
  75.         double distance = Util.distance(point1, point2);
  76.         if (distance < bestDist)
  77.           bestDist = distance;
  78.       }
  79.     }
  80.     return bestDist;
  81.   }
  82. }
  83. //
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top