## Instructions

**Objective**

## 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)