Academic Integrity

Before attempting to solve the assignment, please read the message below very carefully.

As described on https://academicintegrity.cs.auckland.ac.nz/, you must NOT

Last year, out of 218 students, there were 20 misconducted cases found on Task 1 and 18 misconducted cases found on Task 2.   we kept the submissions from the last few years to run MOss at https: //theory.stanford.edu/~aiken/moss/.

I hope that there will be no cases this year!

Requirements

This 4th assignment lets you get familiar with divide-and-conquer design and development. It is worth 5% of your total course marks.  we would like you to implement efficient divide-and-conquer algorithms for two tasks: Task 1: closest pair in plane and Task 2: counting Intervals. o(nlog n) solutions are preferred since we have set the running time limit on the automated marker.

An excessive number of submissions (over 1o) for a particular problem will accrue a 2o% penalty per that problem if you eventually solve it.  Therefore, please write a bruteforce algorithm and test your divide-and-conquer version with your own generated inputs at scale before submitting to the automated marker.

1 Task 1: closest pair in plain

1.1    problem description

This is the closest pair problem in the lecture. Your input will be a sequence of 2D points, each given on its own line, coordinates are separated by one space.  The coordinates are integers (ranging from -231 to 231 ). You should output the minimum squared Euclidean distance so that the automated marker would not trouble with the double-precision.

1.2    Test case description

There are 3 test cases for the closest pair.

1.  A trial test case of 1o points has no mark.

2.  A test case of 1ook points has 1 mark.

3.  A test case of 1oook points has 2 marks.

sample Input 1:

3  2

0  0

5  7

0  2

sample output 1:

4

sample Input 2:

-3  2

-10  -100

-5  -7

0  2

sample output 2:

9

2 Task 2: counting intervals

2.1 problem description

In this task, your input includes a list of n intervals [x, g) where x is the starting point and g is the ending point. Given a list of n query points, for each query q, you need to report the number of intervals containing q.  In other words, you will return the number of intervals  [x, g) such that x 三 q < g. To simplify the task, there are no duplicates of starting and ending points among all n intervals. The values x , g , q are loats with maximum 4 decimal places.

your input will start with the value of n, continuing with n intervals, and n queries.  For each interval, loat coordinates x and g are separated by one space.

For each query q, you should output an integer  (from o to n) that counts the number of intervals containing q. Given an array counteT for n queries, a python script to output should be:

for x  in  counter:

print（x）

2.2 Test case description

There are 2 test cases for the counting intervals task.

1.  A trial test case of n = 1o has no mark.

2.  A test case of n = 1o, ooo has 2 marks. we expect the algorithm runsin O(nlog n) time, especially each query uses O(log n) operations.

sample Input 1：

4

1  3

2  5

7  8

9  10

2

4

8

9

sample output 1：

2

1

0

1

Note that sample Input 1 is an example for getting the output.  your test cases are like the sample Input 2.

sample Input 2：

4

1.2345 1.1234 2.4567 1.0001 2.1234 3.1234 4.1234

1.1231

2.3456

2.2345

3.1234

3.2345