Problem: Optimal Power Line Location The power distribution company is planning to build a main power line from east to west (parallel to the x-axis) across its distribution area The area has n houses of 3 different sizes. The company wants to connect each house directly to the main power line with smaller power lines in north-south direction (parallel to the y-axis) The cost of each small power line is proportional to the distance of the house (from its center point) to the main power line and also the size of the house (larger houses require more power and thus better quality cables etc.). The cost of a small power line = (Distance) (size of house) The size of a house = 1, 2, or 3 (representing 1000, 2000, or 3000 square feet) The goal is to estimate the optimal position (y-coordinate) of the main power line so that the total cost of the small power lines is minimum.

Goal: Write a program .java that takes as input the following: In the first line, the number of houses n, with 2 n 1, 000, 000 In each consecutive line (from 2nd to (n + 1)-th line), the y-coordinate of one houses center point (integers in the range 0 to 1,000,000,000) and the size of the house (1, 2 or 3) Returns as output: A single number: the y-coordinate where the main power line should be built Just one number, no comments, prompts etc. Use a file input.txt to read input (which should be displayed in the file as mentioned above and as shown in the example below) and write the result to the console Make sure the program compile.

Approach: Start with the case where the size of all houses is 1 Work over examples towards the solution (see sample example above) Consider the y-coordinates of houses (their center points) as an array of size n Design a divide & conquer algorithm like quicksort Use a recursive approach with an appropriate partition-like method Look for asymptotically the fastest method. Your solution should have linear time O(n) complexity on average. Note: It must be implemented so that it is O(n) on average, but you do not need to provide a proof for that. Slower methods will not get full credit even if they are correct. There may be several correct solutions (i.e., y-coordinates of the main power line), return one of them (each one gets full credit). Taking the average or weighted average of the y-coordinates of the houses will not work! Example: 5 houses (same size) at y locations: 1, 1, 1, 1, 11. Average of locations is 3, but optimal location is 1.

Example