• API
• FAQ
• Tools
• Archive
daily pastebin goal
18%
SHARE
TWEET

# Pasty

a guest Dec 12th, 2018 54 in 77 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++) {
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) {
44.       i++;
45.     }
46.     while (i < points.size()) {
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) {
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.

Top