Land Division#1278
The king of the Far, Far Away Kingdom has passed away, and the kingdom must be divided among his sons. The kingdom, which can be represented as a rectangular map, consists of cities. To divide the land, they will draw K-1 straight segments on the map, each parallel to either the vertical or the horizontal axis. This divides the map into exactly rectangles, all having equal heights (if the dividing lines are vertical) or equal widths (if the dividing lines are horizontal). No segment may pass through any of the cities. Each son will then be randomly assigned one of the regions, and the cities inside that region will be his share.
Of course, they want the division to be as fair as possible: theoretically, in the fairest division, each son should get cities (we'll call this value the baseline), but since the baseline is not always an integer, each of the sons wants to be as close as possible to the baseline. The unfairness for each son is calculated as the absolute difference between the number of cities assigned to him and the baseline. The fairest division is the one that minimizes the average unfairness of all sons.
Consider the example above with sons and cities (so the baseline is 6/3 = 2.0). Figure (a) shows the original map. Figure (b) shows a non-optimal division (the dashed lines are the dividing lines). In this case, the middle region contains cities (unfairness |3 - 2| = 1), the left region contains city (unfairness |1 - 2| = 1), while the right region contains cities (perfectly fair, unfairness ), so the average unfairness is .
Figure (c) on the right shows the optimal division since all three regions contain the same number of cities, and the average unfairness is .
Write a program to determine the fairest land division for a given kingdom.
Your program will be tested on one or more test cases. Each test case is described on N+1 lines.
The first line of each test case specifies two positive integers: N \leq 100\,000 and K \leq 10, where is the number of cities and is the number of children. Note that K \leq N.
Then lines follow, each describing the coordinates of a city specified by two integers , where 0 \leq x, y \leq 100\,000. Since coordinates are rounded to the nearest integer, more than one city could have the exact same coordinates on the map. You may assume the map of the kingdom is any rectangle containing all of the given points (although this information is not needed by the program). Note also that while all cities lie on integer coordinates, the dividing lines need not be.
The last line of the input file contains two zeros.
For each test case, print the following line:
k. A/B
Where is the test case number (starting from ), and is the minimum average unfairness that can be obtained. should be an irreducible fraction. Let B=1 when the result is an integer.
Note: There is a space before .
Beispiel 1