National Olympiad in Informatics, China, 2004
Day 2, Problem 2 - Little H's Little Hut
Little H vowed to become the greatest mathematician of the 21st century. He believed that being a mathematician is like being a pop star - the first step is to focus on appearances, otherwise, no matter how much talent you have, you still won't be able to sell it. Knowing this, he decided to put work into his domicile, so that anybody at a glance will be able to tell that a "great future mathematician" lives inside it.
For the sake of clarity, we let east be represented by the positive x direction, and north be represented by the positive y direction, establishing a Cartesian coordinate system. Little H's little hut, when measured from east to west, is 100Hil long (Hil is little H's own unit of length; as for how to convert it to meters, nobody knows). The east and west wall are parallel to the y axis. The north and south walls are straight lines with real number slopes k1 and k2 respectively. Along the north and south walls, there are many patches of grass, each rectangular in shape and parallel to the axes. The meeting points of adjacent patches of grass just happen to be points along the walls. The x-coordinates of these meeting points shall be called "division points", and these division points must be integers from 1 to 99.
Little H believes that only through the combination of symmetry and asymmetry can "mathematical beauty" be achieved. Thus, along the north wall there needs to be m patches of grass, and along the south wall there needs to be n patches of grass, where m ≤ n. If the division points of the north and south walls are respectively placed into sets X1 and X2, then they should satisfy X1 ⊆ X2. That is, any division point from the north wall should also be a division point on the south wall.
Since little H does not currently have a substantial income, he must minimize the total cost of creating the grass patches. He intends to do so by ensuring that the total area occupied by the grass is as small as possible. Can you write a program that helps him resolve this dilemma?
The input will consist of a single line containing 4 numbers k1, k2, m, and n. k1 and k2 are positive real numbers describing the slopes of the north and south walls respectively, accurate to 1 decimal place. m and n are positive integers describing the number of patches of grass are along the north and south walls of the hut respectively.
The output should consist of one real number, representing the minimum possible area of the ground occupied by the grass. This must be displayed to one decimal place, and must be within an error of ±0.1 from the actual answer.
- 2 ≤ m ≤ n ≤ 100
- The north and south walls are really far apart. There will not be a scenario where grass patches from the north and south walls overlap.
0.5 0.2 2 4
Point Value: 20 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: May 19, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3