Problem Statement |
| | Two brothers have a garden containing several profitable fruit trees. The garden can be represented as a plane, where each tree is a point. The brothers have decided to divide the garden into two parts using a straight line. No trees must lie on that line. One brother will then receive all the income from the trees on one side of the line, and the other brother will receive all the income from the trees on the other side of the line.
You are given int[]s x, y and income, where (x[i], y[i]) are the coordinates of the i-th tree, and income[i] is the annual income generated by the i-th tree. Return the minimal possible absolute difference between the total annual incomes of the brothers.
|
| |
Definition |
| | | Class: | TreesDivision | | Method: | minDifference | | Parameters: | int[], int[], int[] | | Returns: | int | | Method signature: | int minDifference(int[] x, int[] y, int[] income) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | x will contain between 2 and 50 elements, inclusive. |
| - | x, y and income will all contain the same number of elements. |
| - | Each element of x will be between 0 and 1,000, inclusive. |
| - | Each element of y will be between 0 and 1,000, inclusive. |
| - | Each element of income will be between 1 and 1,000,000 inclusive. |
| - | All the points (x[i], y[i]) will be distinct. |
| |
Examples |
| 0) | |
| | | Returns: 10 | | Draw a line so that the two points are on different sides. The absolute difference between the total annual incomes of the brothers will then be 20-10=10. |
|
|
| 1) | |
| | {0,1,2,3} | {1,1,1,1} | {1,1,1,1} |
| Returns: 0 | |
|
| 2) | |
| | {0,0,0,0,0} | {1,2,3,4,5} | {1,2,3,4,1000} |
| Returns: 990 | | The first brother can get the first four trees. In this case, the absolute difference will be |(1+2+3+4)-1000|=990. |
|
|
| 3) | |
| | {0,0,1,1} | {0,1,1,0} | {1,2,4,8} |
| Returns: 1 | |
|
| 4) | |
| | {4,2,4,2,3,6,3,5} | {1,2,4,3,3,2,4,5} | {4,5,2,6,7,4,2,4} |
| Returns: 2 | | Draw a line that passes through points (4,0) and (2,7). One brother will get trees 1, 3 and 4 (0-indexed) for a total income of 5+6+7=18. The other brother will get all of the remaining trees for a total income of 4+2+4+2+4=16. |
|
|
| 5) | |
| | {1,2,3} | {3,2,1} | {1,1000000,1} |
| Returns: 1000000 | |
|