Farmer Brown has many rectangular pastures.
Two pastures are connected if they share a border (two pastures which share a corner are not connected). A super pasture is a maximal connected set of pastures. In other words, for every two pastures in a super pasture there exists a continuous path which connects these 2 pastures and never leaves the super pasture. If a pasture is not connected with any other pasture, it is considered to be a super pasture itself.
The diagram above contains 9 pastures, which form 3 super pastures. Pasture 0 does not share borders with any other pasture, and forms a super pasture itself. Pastures 1, 2, 3, 5 and 7 form another super pasture, while pastures 4, 6 and 8 form the third super pasture. Please note that pastures 0 and 6 are not connected because they share only a corner.
The badness of a super pasture is the area of its bounding rectangle minus the sum of the areas of its pastures. For example, if a super pasture is formed by only 1 pasture, it has a badness of 0. The super pastures in the diagram have badnesses of 0, 10 and 5, respectively.
Farmer Brown has decided to sell one of his pastures. To choose the pasture he will sell, farmer Brown has the following rules:
See the examples for further clarification.
- The pasture must belong to the super pasture with the highest badness. If several super pastures have the maximal badness, he can choose a pasture from any of them.
- Selling the pasture must not break a super pasture apart.
- Among the pastures which satisfy the first two conditions, he will choose the pasture with the smallest area. In case of a tie, he will choose the pasture with the lowest index.
You will be given a String pastures containing the information about all of farmer Brown's pastures. Each element of pastures will be formatted like "a b c d", where a, b, c and d will represent the leftmost, the rightmost, the topmost and the bottommost coordinates of the pasture, respectively. In other words, the pasture is a rectangle with two corners at (a, c) and (b, d).
Your program should return the 0-based index of the pasture farmer Brown will sell.