Description
Optimal Power Line Location
• Power distribution company is planning to build a main power line
from east to west (x-axis) across its distribution area
• The area has n houses
• The company wants to connect each house directly to the main
power line with smaller power lines in north-south direction (y-axis)
• Your task is to estimate the optimal position (on the y-axis) of the main power line, so that the total length of smaller power lines is
the shortest.
9/28/18 2
Assignment 2
Write a program cmsc401.java that
• takes as input
– in the first line, the number of houses n, n>=2, n<1,000,000
– in each consecutive line (from 2nd to (n+1)-th line), the y- coordinate of one house (integers in the range 0 to
1,000,000,000)
• returns as output
– a single number: the y-coordinate where the main power line should be built
– only one number, no comments, prompts etc.
• Use standard I/O to read input (System.in, System.out) and
write the result
• Make sure the program compiles
9/28/18 3
Example
Input
6
1
8
3
6
2
7
9/28/18 4
y=2
y=3
y=8 y=7
y=1
y=6
y=5
Output
5
Total length of smaller power lines: 15
This is the minimum possible length.
There might be other results with the same minimum
Hints
• Think about the solution over examples
• Consider the y-coordinates of houses as an array of size n
• Design a divide & conquer algorithm like
quicksort
– Use recursive approach with an appropriate Partition- like method
• Try to use the asymptotically fastest method
– Aim at expected linear time O(n)
– Slower methods will get lower score even it is correct
• There may be several correct solutions, return one
of them.
9/28/18 5
Submission
• Date due: Friday, Oct 12th, 11:59 pm
• Upload through Blackboard
– Submit as a zip file with name 2_FamilyName_FirstName.zip and
include
• Java source code in a single file cmsc401.java (all lower case letters!)
• The file should have your name in a comment in the first line
• Remember: in Java, class name should match the file name, and is case
sensitive
• Please do NOT create your own packages
• Do NOT place the file into a folder – just zip the file
• Use standard I/O to read input (System.in, System.out) and output
• Make sure the program compiles and WORKS!
• Late submissions are accepted up to 2 days!