- Notifications
You must be signed in to change notification settings - Fork19.9k
Added RandomizedClosestPair code and test#6224
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
base:master
Are you sure you want to change the base?
Added RandomizedClosestPair code and test#6224
Uh oh!
There was an error while loading.Please reload this page.
Conversation
codecov-commenter commentedApr 17, 2025
Codecov ReportAttention: Patch coverage is
Additional details and impacted files@@ Coverage Diff @@## master #6224 +/- ##============================================+ Coverage 73.81% 73.85% +0.03%- Complexity 5311 5325 +14============================================ Files 673 674 +1 Lines 18376 18421 +45 Branches 3553 3562 +9 ============================================+ Hits 13565 13604 +39- Misses 4264 4267 +3- Partials 547 550 +3 ☔ View full report in Codecov by Sentry. 🚀 New features to boost your workflow:
|
DenizAltunkapan left a comment• edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Thanks for contributing!
Please fix the pipeline (GitHub Actions) and adjust the requested changes so that the Checkstyle rules will pass. The rest looks pretty good to me 🙂@Jivi-this-side
| } | ||
| public static class Point { | ||
| public final double x, y; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Each variable declaration must be in its own statement. Please split these two declarations.
| Point[] Qx = Arrays.copyOfRange(px, 0, mid); | ||
| Point[] Rx = Arrays.copyOfRange(px, mid, n); | ||
| List<Point> Qy = new ArrayList<>(); | ||
| List<Point> Ry = new ArrayList<>(); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
please write qx instead of Qx because this is not camelCase.
| if (p.x <= midPoint.x) Qy.add(p); | ||
| else Ry.add(p); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
'if' construct must use '{}'s (see checktyle)
| private static double distance(Point p1, Point p2) { | ||
| return Math.hypot(p1.x - p2.x, p1.y - p2.y); | ||
| } | ||
| } |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Line has trailing spaces according to checkstyle, please remove this
| double result = RandomizedClosestPair.findClosestPairDistance(points); | ||
| assertEquals(5.0, result, 0.00001); | ||
| } | ||
| } |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Line has trailing spaces according to checkstyle, please remove this
So, how is it going?@Jivi-this-side |
Uh oh!
There was an error while loading.Please reload this page.
clang-format -i --style=file path/to/your/file.javaRandomized Closest Pair of Points : (As per issue#6219 added this algo to repo)
The Closest Pair of Points problem finds the minimum Euclidean distance between two points in a 2D plane.
Randomized Algorithm Approach:
Randomly shuffle the input points.
Use a sweep-line + grid bucketing strategy to maintain only nearby points for efficient lookup.
Continuously update the closest pair distance while sweeping from left to right.
⚡ Time Complexity
Expected Time: O(n)
Worst-case Time: O(n log n)
Use Cases
Geospatial clustering
Nearest-neighbor search
Computational geometry in games, simulations, and robotics
Thank you!