Limits: 1s, 256 MB
Quido has a square orchard full of various fruit and nut trees. The trees are planted in regular rows and columns forming a rectangular grid. There are as many rows as there are columns. To be able to maintain the orchard more easily Quido wants to divide the orchard into four rectangular parts. First, he will divide the orchard into northern and southern part by one straight path running from east to west between two rows of the trees. Next, he will divide the northern part by one straight path running from the north perpendicularly to the east-west path. The southern part will be divided similarly by a straight path running from south perpendicularly to the east-west path. These two additional path need not to meet at the same point. The resulting situation might look like the one in the picture bellow. Quido has assigned a quality index to each tree, the index may be positive or negative or zero. The quality of each of four parts of the orchard will be the sum of qualities of all trees in that part. Quido wants the resulting parts to be of similar quality, in fact, he wants the qualities of the four parts be as close to each other as possible. Therefore, he must choose the positions of the three dividing paths according to this demand.
This is a companion discussion topic for the original entry at https://toph.co/p/orchid-division