#P4274. [NOI2004] 小H的小屋

    ID: 3205 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 8 上传者: 标签>动态规划,dp贪心2004NOI 系列模拟退火

[NOI2004] 小H的小屋

Description

Little H swears to become the greatest mathematician of the 21st century. He believes that, just like singers, mathematicians need good packaging; otherwise, no matter how capable you are, you cannot get noticed. Therefore, he decides to start with his residence so that at a glance people know a "future great mathematician" lives inside.

For convenience, we set the positive direction of the xx-axis to the east and the positive direction of the yy-axis to the north, establishing a Cartesian coordinate system. Little H's house is 100100 Hil long from east to west (Hil is Little H's own unit of length; as for how it converts to "m", nobody knows). The east and west walls are both parallel to the yy-axis, and the north and south walls are lines with slopes k1k_1 and k2k_2, where k1k_1 and k2k_2 are positive real numbers. There are many lawns at the corners along the north wall and the south wall; each lawn is a rectangle whose sides are parallel to the coordinate axes. The contact points of adjacent lawns lie exactly on the wall, and the xx-coordinates of these contact points are called the wall's "division points". These division points must be integers from 11 to 9999.

Little H believes that the combination of symmetry and asymmetry best reflects "mathematical beauty". Therefore, there must be mm lawns along the north wall corners and nn lawns along the south wall corners, with mnm \leq n. If we denote the sets of division points on the north and south walls by X1X_1 and X2X_2 respectively, then they must satisfy X1X2X_1 \subseteq X_2, that is, every division point on the north wall must also be a division point on the south wall.

Since Little H does not yet have a large income, he must minimize the construction cost of the lawns, i.e., minimize the total area occupied by the lawns. Can you write a program to help him solve this problem?

Input Format

A single line containing 44 numbers k1k_1, k2k_2, mm, nn. The numbers k1k_1 and k2k_2 are positive real numbers representing the slopes of the north and south walls, accurate to one decimal place. The numbers mm and nn are positive integers representing the number of lawns along the north wall corners and the south wall corners, respectively.

Output Format

A real number, the minimal total area occupied by the lawns, to one decimal place.

0.5 0.2 2 4
3000.0

Hint

Conventions

2mn1002 \leq m \leq n \leq 100.

○ The distance between the north and south walls is very large; there will be no overlap between lawns near the south wall and those near the north wall.

Translated by ChatGPT 5