ENGG1330 Computer Programming I
2nd Semester
Assignment 2:
Due date: 30-April-2019, 23:55. Late submission: 10% discount per day, No submission will be accept after 2-May-2019, 23:55
One day, farmer Peter got an agricultural land from his friend and he plans to divide the land into numbers of field for planting different crops. The land has numbers of non-removable stones that can be used to build the partitions of fields. To make it simple, field will be in form of rectangle with its sides either parallels to x-axis or y- axis. The corners of a field must build on a stone. Fields can share partition and having stone placed inside but cannot be overlapped. For example, the land shown below got 9 stones in the middle and four possible fields can be made.
XX XXX
XXXX
XX XX XXX XXX
XXXX XXXX
XX XX XXX XXX
XXXX XXXX
Without overlapping, the final partition of land can be either partition A or B shown below. However, partition A is more preferable as it gives more area for farming.
1
Partition A Partition B
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
or
After investigated the land closely, Peter found that it is too difficult for him to work out the best partition and therefore, he asks for your help again. As an engineering student, you decide to solve it by writing a computer program.
Input:
The first input would be the number of stones in the land, n, followed by n pairs of unsorted stone¡¯s coordinate. The coordinate is inputted as x and y separated by a space, i.e. “x y”, with the origin on the bottom left corner of the land. Both n, x and y are integers. You may assume that n<100 and total number of possible fields in a given land should be less than 100.
Example: 9
22
25
42 44 94 62 64 65 92
2
A. Write a program to output the numbers of possible fields (rectangle) that can be built on a given land. The sample input and output of 4 lands are shown below.
#1 #2 XX
XX XXXX
XXXXX #3 #4
XX
X XXX
X XXXX
Input
192 22
25 42 44 92 94 96 10 4 10 6
240 22
25 42 44
320 44
22
494 22
25 42 44 94 62 64 65 92
Output
3
B. Write a program to work out the largest framing areas of a given land. The program should select a list of fields so that:
a. Fields in the list are not overlap with each other.
b. The total area of the selected fields is the largest possible framing area of
the given land.
In case more than one partitioning have the largest farming area, select the one with larger individual farming area. The program should output the number of non-overlapped fields, followed by the area of each field in a descending order.
Input Output
1
9 22 25 42 44 92 94 96 10 4 10 6
2 10 2
2
4 22 25 42 44
0
3
2 44 42
0
4
9 22 25 42 44 94 62 64 65 92
2 12 6
4
II. Submission
Virtual Programming Lab (VPL) will be setup for each part. However, we encourage you to test your program with your own test cases before submit your program. Your program should generate the output based on the specifications, i.e. without extra text/space. We may mark your program with test cases different from those found in VPL.
Plagiarism (detected by the system) will get zero marks, apply to the source providers as well.
5