TreesDivision
SRM 432 · 2009-01-06 · by nika
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
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.
{1,2}
{2,3}
{10,20}
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.
{0,1,2,3}
{1,1,1,1}
{1,1,1,1}
Returns: 0
{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.
{0,0,1,1}
{0,1,1,0}
{1,2,4,8}
Returns: 1
{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.
Submissions are judged against all 92 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TreesDivision with a public method int minDifference(vector<int> x, vector<int> y, vector<int> income) · 92 test cases · 2 s / 256 MB per case