Description

The Beijing–Zhuhai Expressway is currently under construction. The Yuebei region is a world-famous “Danxia landform,” and the expressway must pass through a large, complex mountainous area here. The chief designer Bonny has planned the general route of the highway, and engineers have been dispatched to various mountainous sections to design the detailed plans for these segments.

Now, thanks to your outstanding achievements in informatics, Bonny assigns you to the most complex section called DreadfulMess, giving you only a map and some data.

The map is described in a Cartesian coordinate system. It includes the data of all mountains in this region (top view) and two points A and B. Each mountain’s outline is approximated by a quadrilateral, and the engineers call the vertices of these quadrilaterals “survey points.” The quadrilaterals do not overlap or contain one another, but they may share an edge segment or a vertex. Areas outside the mountains are considered flat ground.

Your task is to compute the total area of the mountainous region of this segment and to design a highway starting at point A and ending at point B. The design principles are:

1. The highway is a polyline (i.e., the number of turning points is finite).
2. The highway may be built on flat ground, along foothills or valleys (i.e., the junction of two mountains), or by tunneling.
3. Tunnel portals cannot be turning points unless they are also survey points.
4. The construction cost should be minimized.

Cost calculation: The unit construction cost on flat ground or along foothills or valleys is $u_0$, and the unit tunneling cost through the $i$-th mountain is $u_i$.

Input Format

• The first and second lines are the coordinates of points A and B, respectively, both integers.
• The third line contains $u_0$, a positive integer.
• The fourth line contains the number of mountains $n$, with $0\leq n\leq 50$.
• The next $n$ lines: each line first contains a positive integer $u_i$, then $8$ integers giving the coordinates of the quadrilateral’s vertices in counterclockwise order.

The input guarantees that points A and B are not inside any mountain, no three vertices of any quadrilateral are collinear, and the absolute value of every integer does not exceed $1000$.

Coordinates are given as pairs of integers: the first is the $x$-coordinate, and the second is the $y$-coordinate. If there are multiple adjacent integers on the same line, they are separated by at least one space.

Output Format

• The first line is the total area of all mountains in the region.
• The second line is the total length of the designed highway.
• The third line is the construction cost of the designed highway.

All outputs should keep two decimal places.

-10 1
10 1
100
2
110 0 0 -5 5 -10 0 -5 -5
300 5 -5 10 0 5 5 0 0

100.00
21.93
2252.15

Hint

Translated by ChatGPT 5