Problem Set 5(Minimum Distance)

Minimum Distance Points

Given 'n' points in an X-Y plane , write an algorithm and the subsequent Python code to determine the pair of points that are closer. Distance between two points (x1, y1) and (x2, y2) is determined using the formula.

Consider only two decimal places of distance for comparison. When there are multiple points with the same minimum distance print all points.

Input Format

Number of points

x coordinate of point1

y coordinate of point1

x coordinate of point2

y coordinate of point2

...

Output format

Point1 and Point2 that have minimum distance between them

Input:

the number of points n, the corresponding n points

Processing:

points = []

for i in range(n):

    x = int(input())

    y = int(input())

    points.append((x,y))

final_points = []

for i in range(len(points)):

    for j in range(i+1,len(points)):

        dist = ((points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2)**0.5

        if i == 0 and j == 1:

            distance = dist

            minimum = dist

        else:

            if distance >= dist:

                if distance == dist:

                    final_points.append(points[i])

                    final_points.append(points[j])

                else:

                    final_points = []

                    final_points.append(points[i])

                    final_points.append(points[j])

                distance = dist

if minimum <= distance:

    final_points.append(points[0])

    final_points.append(points[1])

Output:

Display the two points with minimum distance

Algorithm: 

Step1. Get the number of points

Step2. Initialize points as an empty list and i as 0

Step3. Repeat till i is less than n

Step3.1. get the x and the y coordinates of the point

Step3.2. insert the x,y coordinates into points list

Step4. Sort the points list

Step5. Assign i,j as 0,i+1

Step6. Repeat till i is less than length of the points list

Step6.1. repeat till j is less than length of the points list

Step6.1.1. assign dist as the distance between the ith and the jth point in the points list

Step6.1.2. if i is equal to 0 and j is equal to 1 then assign distance as dist and minimum as dist else proceed to step6.1.3.

Step6.1.3. if distance is greater than or equal to dist the proceed to step6.1.4

Step6.1.4. check if distance is equal to dist if yes then proceed to 6.1.5 if no then proceed to 6.1.6

Step6.1.5. if points[i] is not in the final_points list then append it to the list and do the same for points[j]

Step6.1.6 reinitialize final_list as an empty list and then append the points in the list

Step7. display the points with minimum distance

Step8. end

Program:
n = int(input())
points = []
for i in range(n):
    x = int(input())
    y = int(input())
    points.append((x,y))
final_points = []
for i in range(len(points)):
    for j in range(i+1,len(points)):
        dist = ((points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2)**0.5
        if i == 0 and j == 1:
            distance = dist
            minimum = dist
        else:
            if distance >= dist:
                if distance == dist:
                    final_points.append(points[i])
                    final_points.append(points[j])
                else:
                    final_points = []
                    final_points.append(points[i])
                    final_points.append(points[j])
                distance = dist
if minimum <= distance:
    final_points.append(points[0])
    final_points.append(points[1])
for i in final_points:

    print(i)