# Lab 0

This is a warm up, ungraded, lab.

Submission deadline: 2359, Friday, February 2, 2018.

## Learning Objectives

After completing this lab, students should:

- be more comfortable with the CS2030 laboratory environment, including knowing how to remotely access
`cs2030-i`

, create directory, copy files, edit files, transfer files between`cs2030-i`

and local computers, run a script, and other UNIX commands - be familiar with compiling and running Java programs from the command line
- be familiar with the concept of standard input and standard output, how to redirect the content of a file to standard input, and how to print to standard output
- be more comfortable with basic Java syntax and semantics, specifically with
- adding methods into existing classes
- invoking the methods of the classes to solve problems
- declaring and using arrays, primitive types, and objects
- using if/else and for statements
- printing to standard output
- the
`this`

keyword

- adding methods into existing classes
- experience reading Java API documentation and find out what are the methods available, and what are the arguments and returned types.
- see an example of how class
`Scanner`

is used - appreciate how encapsulation of class
`Point`

and class`Circle`

allows one to reason about higher-level tasks without worrying about lower level representation

## Setup

Login to `cs2030-i`

, copy the files from `~cs2030/lab0`

to your local directory under your home `~/lab0`

. You should see four java files (`Point.java`

, `Circle.java`

, `MaxDiscCover.java`

, and `LabZero.java`

), and a few data files (`TESTDATA1.txt`

, `TESTDATA2.txt`

, ..., `TESTDATA5.txt`

)

Read through the files above. Although we have seen `Circle`

and `Point`

as examples in class, these classes are slightly different.

## 1. Augment the class Point

Augment the class `Point`

with the following public methods and constructors.
You may find the static methods provided by `java.lang.Math`

useful.

### 1.1. Static Method to construct mid point

1 | public static Point midPoint(Point p, Point q) |

Given two points `p`

and `q`

, create and return the midpoint of `p`

and `q`

.

### 1.2 Distance between points

1 | public double distanceTo(Point q) |

You should have written something like this from your Exercise 1. This method returns the Euclidean distance of `this`

point to the point `q`

.

### 1.3 Angle between points

1 | public double angleTo(Point q) |

This method returns the angle between the current point and point `q`

. In the figure below, it returns the angle \theta. You can compute this using the `atan2()`

function. For instance,

1 2 | Point p = new Point(0, 0); p.angleTo(new Point(1, 1)); |

1 | 0.7853981633974483 |

1 | p.angleTo(new Point(1, 0)); |

should return

1 | 0.0 |

`atan2()`

takes in two `double`

as arguments for coordinate `x`

and `y`

. It returns `theta`

, the angle in radian, counted in
anti-clockwise direction with respect to origin. One mathematical trick here is if you subtract the coordinates
of `Point p`

from `Point q`

, you basically reduce `Point p`

to be an origin to `Point q`

.
For more detail, please refer to the Java API for `atan2`

for more details.

### 1.4. Move a point

1 | public void move(double theta, double d) |

Move the point by a given distance at direction theta (in radian). See Figure:

The new point should have the coordinate (x + d\cos\theta, y + d\sin\theta). Note in this method, you are given the angle (theta) and want to find length. Hence you need to use cosine and sine.

After

1 | p.move(p.angleTo(q), p.distanceTo(q)); |

`p`

should coincide with `q`

.
Mutable vs. Immutable

The method `move`

is called a *mutable* method, since it modifies (mutates) the object that it is called on. Later in CS2030, you will be introduced to the concept of *immutable* methods.

## 2. Augment the class Circle

Augment the class `Circle`

with the following methods and constructors:

### 2.1 Constructor

1 | public Circle(Point p, Point q, double radius) |

The constructor above takes in two points `p`

and `q`

, and returns a circle that passes through both `p`

and `q`

, with radius `radius`

.

There are two such possible circles (see figures below) if distance between `p`

and `q`

is no greater than 2x`radius`

^{1}. Imagine if you walk from `p`

to `q`

, one of the circle will have the center on your left, the other will have the center on your right. In this method, 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`

. See figure below.

Hint: To find the center c of the new circle, you can first find the midpoint m of line pq, the length of line mc, and the angle between m and c, using the `Point`

methods you have written. We also know that length of cq is `radius`

. See figure below.

The constructor should return a `Circle`

with Double.NaN as the radius and (0,0) as center if the distance between `p`

and `q`

is larger than 2x`radius`

or is zero^{2}. Such `Circle`

objects are invalid, and you may want to add a method in the `Circle`

class to check for validity. You can use `Double.isNaN`

for check if a double variable is NaN.

## 3. Maximum Disc Coverage

We are now going to use the `Circle`

class and `Point`

class to solve the maximum disc coverage problem. In this problem, we are given a set of points on a 2D plane, and a unit disc (i.e., a circle of radius 1). We want to place the disc so that it covers as many points as possible. 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^{3}. 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 (you have written a constructor that helps you to find such circles).

So, the algorithm simply goes through every pair of points, and for each circle that passes through them, count how many points are covered by each circle.

The skeleton of the main class, called `LabZero.java`

has been given to you. The file `MaxDiscCover.java`

, also given, is where you will implement tha maximum disc coverage solution . These two files are placed in the same directory as `Circle.java`

and `Point.java`

.

The skeleton code reads a set of points from the standard input, in the following format:

- The first line is an integer, indicating the number of points n (n > 2) in the file.
- The next n lines contains the x and y coordinates of n points, one point per line. Each line has two doubles, separated by space. The first double is the x coordinate; the second double is the y coordinate.

You can assume that the format of the input is always correct and there is always at least two points with distance less than 2 between them.

Complete the program by implementing the maximum disc coverage algorithm above, and print the maximum number of points covered to standard output. You can add additional methods and fields for `Point`

and `Circle`

if needed.

1 2 | ooiwt@cs2030-i:~/lab0[xxx]$ java LabZero < TESTDATA1.txt 2 |

The test cases and answers should be:

TEST | Max Number of Points |
---|---|

1 | 2 |

2 | 4 |

3 | 12 |

4 | 44 |

5 | 5 |

Note that it is still possible for your solution to be buggy and you still get the same answer as above.

## Adding Methods

You can add new methods as needed into the provided skeleton classes. You should, however, avoid using setters and getters, and must not break the abstraction barrier by exposing any instance field as `public`

.

## Submission

When you are ready to submit your lab, on `cs2030-i`

, run the script

1 | ~cs2030/submit0 |

which will copy your java files (and nothing else) from your `~/lab0`

directory on `cs2030-i`

to an internal grading directory.

You can submit multiple times, but only the most recent submission will be graded for the next lab onwards. This lab is a warm-up lab, which will not be graded.