ABS Problem 4-Closest pair Solved

Problem ID: 4closest

Introduction
It is now spring and what would be a better activity than to have a water gun fight? Thinks everyone else. Who would even like to be hit by water though?, you think. Instead you, godlike as you are, take a step up above the petty human beings and observe this crazy game (from a cloud high above, also known as a balcony with a great view). Shortly you get bored out of you mind and decide to create a betting game with your friend.

After having observed the game for a while you think you have figured out the rules. Each minute all players have to stop somewhere in the field where they play and shoot exactly one shot at someone else. As the guns are not made for shooting long distance everyone tries to hit the very closest person. Before everyone shoot you and your friend will play a game. You win if you can name two people who both will shoot at each other, and otherwise you friend wins.

You soon realize that this is an easy task, since of course the two people with the shortest distance (among all distances between pairs of players) between them obviously will shoot at each other. But as you also like to win you do not tell your friend, of course. So, what is the closest distance between any two players? If you can only answer this question, then the victory will be yours!

Aims
The goals of the lab are:

•    Implementing a divide and conquer algorithm solving the Closest Pair problem.

•    Debugging your code.

•    Structuring your code in a logical fashion.

•    Reason about correctness of your algorithm.

•    Reason about upper bounds for time complexity.

Problem formulation
You are given the coordinates of the N people participating in the silly water pistol battle. You should calculate the minimal distance between two people on the battle ground.

Input
The first line of input consists of a single integer, 2≤ N ≤106, the number of players. Then follow N lines, the i-th line containing two integers, the x- and y-coordinates of the i-th player. All coordinates have absolute value less than 109.

Output
The output should contain a single floating point number containing the shortest distance between two players on the battle field. The output should be a floating point number rounded to exactly 6 decimal digits.

 

Examination and Points of Discussion
To pass the lab make sure you have:

•    Have successfully implemented the algorithm with the correct time complexity.

•    Have neat and understandable code.

•    Have descriptive variable names.

•    Have filled in the blanks in the report.

•    Have run the check_solution script to validate your solution.

During the oral presentation you will discuss the follwoing questions with the lab assistant:

•    What is the time complexity, and more importantly why?

•    Why is it sufficient to check a few points along the mid line?

•    Draw a picture and show/describe when each distance is checked in your solution!

•    When do you break the recursion and use brute force?

Sample Input 1                                                                                 Sample Output 1

4

0 1

0     0

1     0

1 1
1.000000
Sample Input 2                                                                                 Sample Output 2

4

0 -1

-1 0

0     1

1     0
1.414214