## Instructions

### Objective

Write a program to implement distance calculation system in python.

## Requirements and Specifications

**Source Code**

# CS4102 Spring 2022 - Unit A Programming

#################################

# Collaboration Policy: You are encouraged to collaborate with up to 3 other tudents, but all work submitted must be your own independently written solution. List the computing ids of all of your collaborators in the comments at the top of each submitted file. Do not share written notes, documents (including Google docs, Overleaf docs, discussion notes, PDFs), or code. Do not seek published or online solutions, including pseudocode, for this assignment. If you use any published or online resources (which may not include solutions) when completing this assignment, be sure to cite them. Do not submit a solution that you are unable to explain orally to a member of the course staff. Any solutions that share similar text/code will be considered in breach of this policy. Please refer to the syllabus for complete description of the collaboration policy.

#################################

# Your Computing ID: tzc2wh

# Collaborators: tef2nv, maw3rge, tjs9rrr

# Sources: Introduction to Algorithms, Cormen

#################################

```
import math
import copy
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __str__(self):
return f"({self.x},{self.y})"
class ClosestPair:
def __init__(self):
return
# This is the method that should set off the computation
# of closest pair. It takes as input a list containing lines of input
# as strings. You should parse that input and then call a
# subroutine that you write to compute the closest pair distances
# and return those values from this method
#
# @return the distances between the closest pair and second closest pair
# with closest at position 0 and second at position 1
def compute(self, file_data):
secondClosest = 0.1
# Parse all the data so we convert them from string to list of integers
P = map(lambda s: Point(float(s.split()[0]), float(s.split()[1])), file_data)
P = list(P)
P.sort(key = lambda point: point.x)
Q = copy.deepcopy(P)
Q.sort(key = lambda point: point.y)
n = len(P)
#return [closest, secondClosest]
self.distances =set()
closest = self.closest(P, Q, n)
self.distances = sorted(self.distances)
secondClosest = self.distances[1]
return [closest, secondClosest]
def distance(self, p1: Point, p2: Point):
"""
Calculate the euclidean distance between two points
:param p1: Point
:param p2: Point
:return: double
"""
return math.sqrt((p1.x - p2.x)**2 + (p1.y - p2.y)**2)
def brute(self, points):
"""
Given a list of points, return the smallest distance between the closest two pair of points
This method is used only for small amount of points
:param points: List of Point object
:return: tuple
"""
n = len(points)
distances = []
# Compute all distances and add to the 'distances' list
for i in range(n):
for j in range(i+1, n):
p1 = points[i]
p2 = points[j]
dist = self.distance(p1, p2)
self.distances.add(dist)
distances.append(dist)
# Sort in ascending order
distances = sorted(distances)
# Return the first
self.distances.add(distances[0])
return distances[0]
def strip(self, points, n, d):
"""
This function receives a list of points and a maximum distance value 'd'
:param points: List of points
:param d: Maximum distance
:return: double
"""
min_dist = d
for i in range(n):
j = i+1
while j < n and (points[j].y - points[i].y) < min_dist:
min_dist = self.distance(points[i], points[j])
j += 1
self.distances.add(min_dist)
return min_dist
def closest(self, P, Q, n):
if n <= 3:
return self.brute(P)
# Find middle
mid = n//2
pmid = P[mid]
# Split into left and right sides from mid
Pl = P[:mid]
Pr = P[mid:]
# Now, get the smallest distances for left and right sides
dl = self.closest(Pl, Q, mid)
dr = self.closest(Pr, Q, n - mid)
self.distances.add(dl)
self.distances.add(dr)
# Pick the smallest distance
d = min(dl, dr)
# Insert into two arrays the points closer than d to the middle point
stripP = list()
stripQ = list()
lr = Pl + Pr
for i in range(n):
if abs(lr[i].x - pmid.x) < d:
stripP.append(lr[i])
if abs(Q[i].x - pmid.x) < d:
stripQ.append(Q[i])
# Sort in ascending by y coordinate
stripP.sort(key = lambda point: point.y)
min_a = min(d, self.strip(stripP, len(stripP), d))
min_b = min(d, self.strip(stripQ, len(stripQ), d))
self.distances.add(min_a)
self.distances.add(min_b)
# Return
return min(min_a, min_b)
```

## Similar Samples

Explore our diverse array of programming assignment samples at ProgrammingHomeworkHelp.com. These examples exemplify our proficiency in solving coding challenges across different languages and complexities. Whether you're a student needing guidance or a professional seeking reliable solutions, our samples showcase our commitment to delivering high-quality programming assistance tailored to your specific needs.

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python