## Description

Consider the following scenario. You are managing a set of oil wells, each located at some point

(x, y) on a 2D plane. You need to put an expensive fence around your wells. Therefore, you

want to:

– minimize the total length of the fence and

– ensure that every oil well is within your fence.

More precisely, let P = {p1, p2, . . . , pn} be a set of points — they represent the location of the

oil wells. Each pi

is given as a pair (xi

, yi). Your program must be able to output a “fence”

polygon F such that every pi ∈ P is inside or on the boundary of F. Furthermore, you must

ensure that the perimeter of F is minimized.

What does F look like? Consider (as shown below) a rubber band that is stretched around your

points and the released. The rubber band will assume the shape of a polygon that is convex

and encloses every point in P. That polygon is precisely the required output.

1

Notice that the vertices of F will always be some point in P. (Think about why this is the

case.) Also notice that the leftmost point1

is always a vertex in F. (Again, think about why

this is the case.) Therefore, the polygon F is fully described by a sequence of points (that are

all elements of P) starting from the leftmost point2 and tracing the vertices of F in a clockwise

manner.

p1

p2

p3

p4

p5

p6

p7

p8

p9

p1, p2, p3, p4, p5, p6, p7, p8, p9

input = set of points:

output = representation of the convex hull:

p4, p5, p8, p2, p9

In the above figure, the required fence polygon F = (p2, p9, p4, p5, p8). (Note that we don’t

have to repeat p2 at the end as it is assumed that the last point p8 must be connected to the

first point p2 in order to complete the polygon.)

0.1 Command Line Arguments

Your command line argument for this assignment is a single input file name.

0.2 The Input File Format

The input file format includes multiple test cases. Each new test case starts with the keyword

“NewCase” which must be placed in a line without anything else in that line. After the NewCase

line, the input must be a set of points (one per line). Each point must be specified as two

integers with a space between them. When all the points in your test case have been given,

you can either

• start a new test case with the keyword “NewCase” or

• mark the end of all inputs by the keyword “TheEnd” in a line by itself.

The following is a simple example.

NewCase

0 0

5 0

5 5

4 4

NewCase

10 20

15 30

5 40

30 35

TheEnd

1For the purpose of this assignment, assume that there is a unique leftmost point.

2Although you can assume that there is a unique leftmost point, ponder about what might be a good starting

point if there is more than one leftmost point.

2

0.3 Output Format

Your final output must be printed on the screen. The output pertaining to each test case must

be printed each in one line. Thus, with 2 test cases, your output must be of the form:

output line pertaining to test case 1

output line pertaining to test case 2

The format of each line is a clockwise sequence of points (starting from the leftmost) that

form the fence polygon. Since it is well understood that each point is a pair of integers (x, y),

we can simply represent each output line by a sequence of integers. For example, the first test

case in the sample input should give us the following output.

0 0 5 5 5 0

Thus the corresponding output fence polygon F = ((0, 0),(5, 5),(5, 0)) taken in clockwise order.

The above sample input (taking both test cases into consideration) should give you the

following output.

0 0 5 5 5 0

5 40 30 35 10 20

Uploading into MOODLE

Your code should be written as a single .c file. This file must be uploaded into moodle. A link

will be set up for this purpose in moodle.

To Ponder About . . .

What is the running time of your algorithm? Can you think of a faster algorithm?

Your TA for this lab

CS08B031, CS10B052, CS11B001 — CS11B009 Shrikant Polawar

CS11B011 — CS11B021 Sai Sreennivas

CS11B022 — CS11B032 Nishaanth

CS11B033 — CS11B042 Saurav Kant Jha

CS11B043 — CS11B053 Tejas Kulkarni

CS11B054 — CS11B063 Paresh Nakhe

3