CS2030 Lab 1- Maximum Disc Coverage Solution

Topic Coverage
Basic Java syntax and semantics
Object-oriented principles: abstraction and encapsulation
Problem Description

What is the maximum number of points that we can cover with the disc at any one time? We will use the following simple (non-optimal) algorithm. First, some observations:
A disc that covers the maximum number of points must pass through at least two points.
For every pair of points that is of no more than distance 2 away from each other, there is at most two unit discs that have their perimeter passing through the two points.
Given two points p and q, there are are two possible circles. Imagine if you walk from p to q, one of the circle will have the centre on your left, while the other will have the centre on your right. In this task, we will only consider the circle on the left because the circle on the right will be considered when you walk from q to p.

To find the center c of the new circle, first find the mid-point m of the line pq, the length of line mc, and the direction from m to c. The length of cq (or cp) is then the radius.

The Task
Given a set of points as input, go through every pair of points, and for each circle that passes through them, count how many points are covered by each circle.
Input is in the following format:
The first line is an integer, indicating the number of points n (n > 2).
The next n lines contains the x and y coordinates of the n points. Each line has two double values, separated by space. The first double is the x coordinate; the second double is the y coordinate.
Take note of the following assumptions:
The format of the input is always correct;
There are always at least two points with a positive distance less than 2 between them; Output of a double value, say d, are to be formatted with String.format("%.3f", d);
Inconsistencies between sample output and actual output involving -0.000 and 0.000 can be ignored.
This task is divided into several levels. Read through all the levels to see how the different levels are related. You need to complete ALL levels.
In each of the level, you are to
define a Main class with the main method to handle input and output; check for output format correctness using the diff utility (see specific level for usage details). Note that only one test case is provided for this; save a copy of all source files into the appropriate level directory (see specific level for usage details).
Level 1
Represent a Point
Design a class Point to represent a point object with each pair of x- and y- coordinates read from input. Output all the points that is read.
The following is a sample run of the program. User input is underlined.
(0.000, 0.000)
(1.000, 0.000)
Check the format correctness of the output by typing the following Unix command
$ java Main < test.in | diff - test1.out
Make a copy of your Java programs to the level directory by typing the Unix commands
$ mkdir maxcover1
$ cp *.java maxcover1

Level 2
Find the mid-point and angle of line pq
Find the mid-point between two consecutive points p and q read from the input. At the same time, find the angle (in radians) of line pq using the atan or atan2 Math function (refer to the Java API specifications). A jshell interactive session is shown below:
jshell> Point p = new Point(0, 0), q = new Point(1, 1) p ==> (0.000, 0.000) q ==> (1.000, 1.000)
jshell> p.midPoint(q) $4 ==> (0.500, 0.500)
jshell> p.angleTo(q)
$5 ==> 0.7853981633974483
The following is a sample run of the program. User input is underlined.
(0.000, 0.000) and (1.000, 0.000) has mid-point (0.500, 0.000) and angle 0.000
-1 0
(0.000, -1.000) and (1.000, 0.000) has mid-point (0.500, -0.500) and angle 0.785
(1.000, 0.000) and (0.000, 1.000) has mid-point (0.500, 0.500) and angle 2.356
(0.000, 1.000) and (-1.000, 0.000) has mid-point (-0.500, 0.500) and angle -2.356
Check the format correctness of the output by typing the following Unix command
$ java Main < test.in | diff - test2.out
Make a copy of your Java programs to the level directory by typing the Unix commands
$ mkdir maxcover2
$ cp *.java maxcover2


Level 3
Moving the mid-point
With the mid-point and angle of line pq found, we are ready to move the mid-point to the centre of the unit circle whose perimeter coincides with points p and q. In particular, m has to be moved at an angle θ and distance d; you will need to work these values out.
Hint: if m is at (x, y), then moving m at an angle θ and distance d, would result in the new position having the coordinates (x + d cosθ, y + d sinθ)
For each consecutive pairs of points read from input, output the centre of the circle that coincides with the points.
The following is a sample run of the program. User input is underlined.
(0.000, 0.000) and (1.000, 0.000) coincides with circle of centre (0.500, 0.866)
0 1
-1 0
(0.000, -1.000) and (1.000, 0.000) coincides with circle of centre (0.000, 0.000)
(1.000, 0.000) and (0.000, 1.000) coincides with circle of centre (0.000, 0.000)
(0.000, 1.000) and (-1.000, 0.000) coincides with circle of centre (0.000, 0.000)
Check the format correctness of the output by typing the following Unix command
$ java Main < test.in | diff - test3.out
Make a copy of your Java programs to the level directory by typing the Unix commands
$ mkdir maxcover3
$ cp *.java maxcover3
Level 4
Maximum Disc Coverage
With the centre of the circle found, you are now ready to find the maximum unit disc coverage. Just keep in mind that if the distance between points p and q is larger than 2 units, then there is no unit circle whose perimeter coincides with the points.
The following is a sample run of the program. User input is underlined.
Maximum Disc Coverage: 2
-1 0
Maximum Disc Coverage: 4
Check the format correctness of the output by typing the following Unix command
$ java Main < test.in | diff - test4.out
Make a copy of your Java programs to the level directory by typing the Unix commands
$ mkdir maxcover4
$ cp *.java maxcover4