## Description

Optimal Power Line Location

• Power distribution company is planning 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.

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

Example

Input

6

1

8

3

6

2

7

9/27/16 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.

### Submission

• Date due: Tuesday, Oct 11th, 11:59 pm

• Upload through Blackboard

– Your submission should be a zip archive

2_FamilyName_FirstName.zip containing

• Java source code in a file cmsc401.java (all low 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