642 . Xanadu Protector
Description
Charlie the unicorn lives in a beautiful place called Xanadu. What a wonderful land! This
rectangular place is rich in juicy fruits, like banana and papaya. There is a television at the corner
of the land. Charlie the unicorn loves watching TV every afternoon, lazily but comfortably.
Recently, there are some kinds of terrible creatures that are moving to the land. The creatures
include fatal bacteria, strange starfish, fu-gus, and even things with unspoken names like yangyangs
and wawas. Those fierce livings occupy some of the places in Xanadu. They are so disturbing
that Charlie had missed his favorite TV show "Let's go to the candy mountain" ten times already.
Therefore, Charlie the unicorn decides to build some magical fences to keep those creatures out of
his way.
Unfortunately, this kind of fence can only be constructed parallel to one of the edges of Xanadu. Specifically, suppose Xanadu is a rectangular land on the x-y plane with the most south-western point at (0, 0) and the most north-eastern point at (m, n). Then, all the fences may only be built
parallel to the x-axis or the y-axis.
For Charlie's own safety, the fences must form a closed area in Xanadu. Because Charlie the unicorn loves to watch the television without disturbance, the television should be within the closed area while the closed area contains none of the terrible creatures. Furthermore, Charlie the unicorn does not want to give those evil creatures any chance of getting into the area, and hence every point within the area should be under surveillance (directly visible) from the TV. Finally,
the fences should keep a distance of at least d to all the terrible creatures, where the distance between the fences and a terrible creature at (x0, y0) is defined by
However, too many fences on the land would decrease the magic power. Hence, Charlie the unicorn decides not to build more than K fences, where K is an even number. Please help Charlie determine the maximum closed area that he can form with at most K fences. Among all possible ways of building fences that result in the maximum closed area, please also determine the minimum total length of the fences.
Input Format
There is an integer T with 1 <= T <= 100 in the first line. The integer denotes the number of test cases to follow. For each test case, the rst line contains five integers m, n, c, d, K, separated by spaces. m and n indicate the area of Xanadu, c is the number of terrible creatures, d is the
safety distance, and K is the number of fences. Note that 1 <= m, n, d <= 109, 0 <= c <= 5000, and 4 <= K <= 109
where K is even. Each of the next c lines contains a pair of integer coordinates (xi, yi), which indicates the position of each terrible creature, where 0 <= xi <= m and 0 <= yi <= n. The television is always at the point (0, 0).
Output Format
For each test case, please output the maximum area and the minimum total length of fences that achieves the maximum area. You may assume that there is at least one way to construct fences to form a closed area that satisfies all the conditions in the problem.
Sample Input 1
3 10 10 3 1 10 4 8 6 6 10 3 10 10 2 2 4 4 7 6 4 5 7 1 5 4 5 7
Sample Output 1
66 40 20 18 10 14
Hints
You may AC this problem or just put a banana in your favorite ear:)
Problem Source
Migrated from old NTUJ.
NTHU2009, PX
Subtasks
| No. | Testdata Range | Score |
|---|