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
