CSES Solutions β Minimum Euclidean Distance
Given a set of points in the two-dimensional plane, your task is to find the minimum Euclidean distance between two distinct points.
The Euclidean distance of points (x1,y1) and (x2,y2) is sqrt( (x1-x2)2 + (y1-y2)2 )
Example:
Input: points = {{2, 1} ,{4, 4} ,{1, 2} ,{6, 3}};
Output: 2Input: points = {{2, 12} ,{1, 4} ,{3, 2} ,{1, 3}}
Output: 1
Approach:
We can apply sweep-line Algorithm to solve the above problems. We sort the points based on their x-coordinate and we keep a set of the points in the region xβ-βd,βx, sorted by y coordinate. Here d is the smallest distance so far (we can do that with the two-pointers technique). Now, for each new point x,βy, we query the whole range yβ-βd,βyβ+βd in this set and possibly update our answer.
Due to the proof of the Divide and Conquer algorithm, at each time the queried range should be of size O(1) on average, so total complexity would be O(nlog(n)).
Step-by-step algorithm:
- Sort the points based on their X coordinates.
- Initialize a variable to hold the minimum square distance, starting with the maximum possible value.
- Loop through each point.
- Calculate a distance threshold based on the current minimum distance found.
- Create a set to store active points, starting with the first point.
- Iterate through points already considered, removing those that are too far away i.e. more than d.
- Find points within the bounding box defined by the distance threshold.
- Calculate the distance between the current point and points within the bounding box.
- Update the minimum square distance if a closer point is found.
- Print the minimum square distance found.
Implementation:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define Point pair<ll, ll>
#define X first
#define Y second
// Function to calculate the square of Euclidean distance between two points
// Returns the square of the Euclidean distance between two points
ll calculateSquareDistance(Point point1, Point point2) {
return (point2.X - point1.X) * (point2.X - point1.X) + (point2.Y - point1.Y) * (point2.Y - point1.Y);
}
int main(){
// Number of points to consider
ll numPoints = 4;
// List of points
vector<Point> points = {
{2, 1},
{4, 4},
{1, 2},
{6, 3}
};
// Set initial minimum distance to the maximum possible value of a long long integer
ll minSquareDistance = LLONG_MAX;
// Sort the points based on their X coordinates
sort(points.begin(), points.end());
// Create a set to store active points sorted by their Y coordinates
set<Point> activePoints = {{points[0].Y, points[0].X}};
// Initialize a pointer to keep track of points to be removed from the active set
ll j = 0;
// Iterate over the points
for (ll i = 1; i < numPoints; i++) {
// Iterator for the active set
auto it = activePoints.begin();
// Calculate the distance threshold as the square root of the minimum distance
ll dd = ceil(sqrt(minSquareDistance));
// Iterate over points until the distance threshold is met
// Remove points that are too far away
while (j < i && points[j].X < points[i].X - dd) {
activePoints.erase({points[j].Y, points[j].X});
j++;
}
// Find the lower bound of Y coordinates
auto lowerBound = activePoints.lower_bound({points[i].Y - dd, 0});
// Find the upper bound of Y coordinates
auto upperBound = activePoints.upper_bound({points[i].Y + dd, 0});
// Iterate over points within the bounding box
for (auto it = lowerBound; it != upperBound; it++) {
// Update the minimum distance if a closer point is found
minSquareDistance = min(minSquareDistance, calculateSquareDistance({it->Y, it->X}, points[i]));
}
// Insert the current point into the active set
activePoints.insert({points[i].Y, points[i].X});
}
// Print the minimum square distance
cout << minSquareDistance;
}
import java.util.*;
class Main {
static class Point {
long X, Y;
Point(long X, long Y) {
this.X = X;
this.Y = Y;
}
}
// Function to calculate the square of Euclidean distance between two points
// Returns the square of the Euclidean distance between two points
static long calculateSquareDistance(Point point1, Point point2) {
return (point2.X - point1.X) * (point2.X - point1.X) + (point2.Y - point1.Y) * (point2.Y - point1.Y);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Number of points to consider
int numPoints = 4;
// List of points
List<Point> points = new ArrayList<>();
points.add(new Point(2, 1));
points.add(new Point(4, 4));
points.add(new Point(1, 2));
points.add(new Point(6, 3));
// Initialize minimum distance to a large value
long minSquareDistance = Long.MAX_VALUE;
// Sort the points based on their X coordinates
points.sort(Comparator.comparingLong(p -> p.X));
// Iterate over the points
for (int i = 0; i < numPoints; i++) {
for (int j = i + 1; j < numPoints; j++) {
// Calculate the square distance between current points
long squareDist = calculateSquareDistance(points.get(i), points.get(j));
// Update minimum distance if necessary
minSquareDistance = Math.min(minSquareDistance, squareDist);
}
}
// Print the minimum square distance
System.out.println(minSquareDistance);
}
}
class Point:
def __init__(self, X, Y):
self.X = X
self.Y = Y
def calculate_square_distance(point1, point2):
return (point2.X - point1.X) ** 2 + (point2.Y - point1.Y) ** 2
if __name__ == "__main__":
import sys
# List of points
points = [
Point(2, 1),
Point(4, 4),
Point(1, 2),
Point(6, 3)
]
# Initialize minimum distance to a large value
min_square_distance = sys.maxsize
# Sort the points based on their X coordinates
points.sort(key=lambda p: p.X)
# Iterate over the points
num_points = len(points)
for i in range(num_points):
for j in range(i + 1, num_points):
# Calculate the square distance between current points
square_dist = calculate_square_distance(points[i], points[j])
# Update minimum distance if necessary
min_square_distance = min(min_square_distance, square_dist)
# Print the minimum square distance
print(min_square_distance)
class Point {
constructor(x, y) {
this.x = x; // Initialize x-coordinate
this.y = y; // Initialize y-coordinate
}
}
// Function to calculate the square of Euclidean distance between two points
function calculateSquareDistance(point1, point2) {
return (point2.x - point1.x) ** 2 + (point2.y - point1.y) ** 2; // Calculate and return the square of distance
}
const numPoints = 4; // Number of points
const points = [ // Array to store points
new Point(2, 1), // Initialize point 1
new Point(4, 4), // Initialize point 2
new Point(1, 2), // Initialize point 3
new Point(6, 3) // Initialize point 4
];
let minSquareDistance = Number.MAX_SAFE_INTEGER; // Initialize minimum square distance
points.sort((a, b) => a.x - b.x); // Sort points based on x-coordinate
const activePoints = new Set(); // Set to store active points
activePoints.add(points[0]); // Add the first point to active points set
let j = 0; // Initialize pointer for active points
for (let i = 1; i < numPoints; i++) { // Iterate through each point starting from the second point
const dd = Math.ceil(Math.sqrt(minSquareDistance)); // Calculate distance threshold
// Remove points that are too far away
while (j < i && points[j].x < points[i].x - dd) {
activePoints.delete(points[j]); // Delete points that are too far
j++; // Move pointer to the next point
}
const lowerBound = new Point(points[i].x - dd, 0); // Calculate lower bound for x-coordinate
const upperBound = new Point(points[i].x + dd, 0); // Calculate upper bound for x-coordinate
// Iterate through active points within the bounding box
activePoints.forEach(p => {
if (p.x >= lowerBound.x && p.x <= upperBound.x) { // Check if the point is within the bounding box
minSquareDistance = Math.min(minSquareDistance, calculateSquareDistance(p, points[i])); // Update minimum square distance
}
});
activePoints.add(points[i]); // Add current point to active points set
}
console.log(minSquareDistance); // Output minimum square distance
Output
2
Time Complexity: O(n log n), Sorting the points will be O(nlog(n)) and each time the queried range should be of size O(1) on average which can be proved by Divide and Conquer.
Auxiliary Space: O(n), for taking set points.