Mountain Road Design and Area Calculation

The 京珠 Highway project faces a challenging task in the mountainous region where famous Danxia landforms occur. You are assigned to the most complex segment called DreadfulMess. You are given a map in a Cartesian coordinate system which contains the following information:

• Data for m mountains. Each mountain is modeled as a quadrilateral defined by its four measurement points (vertices). The quadrilaterals do not overlap or contain one another, although they may share an edge or a vertex. The area covered by these quadrilaterals is considered mountainous region while outside is plain.
• For each mountain, an integer cost factor u_i is provided which is the unit cost for building a tunnel through that mountain.
• A unit plain cost u_0 is given for constructing roads on plain land, along mountain bases or valleys.
• Two points A and B representing the start and end locations of the road.

Your tasks are twofold:

1. Calculate the total area of the mountainous regions (i.e. the sum of the areas of all the given quadrilaterals using the LaTeX formula \(\text{Area} = \frac{1}{2} \left|\sum_{i=1}^{n}(x_i y_{i+1}-x_{i+1} y_i)\right|\)).
2. Design a road from A to B with minimal construction cost. The road is a broken line (with a finite number of turning points) and can be built using two types of segments:
   • A plain segment built on plain land (or along a mountain's edge) with cost = distance * \(u_0\).
   • A tunnel segment built through a mountain with cost = distance * \(u_i\) (for the mountain in question). However, a tunnel segment can only be built between two measurement points (i.e. mountain vertices) of the same mountain and the interior of the segment (checked at its midpoint) must lie strictly inside the mountain.

   Note: For any straight-line segment between two nodes (either A, B, or a mountain measurement point), if the midpoint falls strictly inside any mountain region then the segment cannot be built as a plain segment. However, if both endpoints are measurement points of the same mountain and the midpoint is strictly inside that mountain, a tunnel segment (with higher cost) may be used. Your solution should choose the route (possibly combining plain and tunnel segments) with the minimum overall cost.

Input Summary:

• First, an integer \(m\) representing the number of mountains.
• Then, for each mountain, a line with 9 integers: the coordinates of the 4 vertices (in order) \(x_1\; y_1\; x_2\; y_2\; x_3\; y_3\; x_4\; y_4\) followed by the tunnel cost factor \(u_i\).
• A line with the integer \(u_0\) representing the plain unit cost.
• A line with 4 numbers: \(A_x\; A_y\; B_x\; B_y\) for the start and end points.

Output Summary:

• Output two real numbers (each with three decimals): the total mountain area and the minimal cost of constructing the road.

Note: Use the standard formula for the area of a polygon (the shoelace formula) and note that all formulas must be written in LaTeX format for any mathematical expressions.

inputFormat

The input is given as follows:

 m
 mountain_1: x1 y1 x2 y2 x3 y3 x4 y4 u₁
 mountain_2: x1 y1 x2 y2 x3 y3 x4 y4 u₂
 ...
 mountain_m: x1 y1 x2 y2 x3 y3 x4 y4 uₘ
 u₀
 Aₓ A_y Bₓ B_y

For example, for one mountain, the input can be:

1
0 0 0 2 2 2 2 0 10
1
-1 1 3 1

outputFormat

Output two floating‐point numbers (each rounded to three decimals) separated by a space:

sample

1
0 0 0 2 2 2 2 0 10
1
-1 1 3 1

4.000 4.828