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.

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 2^nd to (n+1)-th line), the ycoordinate 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

Example

5

Input Output

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 Partitionlike 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.