Minimum Cutting Distance to Achieve a Target Convex Polygon

You are given a rectangle of size \(n \times m\) with its four corners at \((0,0)\), \((n,0)\), \((0,m)\), and \((n,m)\). In the beginning, you have the entire rectangle. Your goal is to obtain a convex polygon with \(p\) sides (with \(p\le 8\)) that lies inside the original rectangle by performing a series of cuts.

In each operation, you choose a straight line that cuts the current polygon into two parts. You then discard one part and keep the other. The cost of a cut is defined as the length of the portion of the cutting line that lies inside the polygon at the time of the cut.

The key observation is that one may always obtain the target polygon by cutting off the extra portions of the rectangle along the supporting lines of the target polygon. Note that if a side of the target polygon coincides with a side of the initial rectangle, then no cut is needed for that side; otherwise, a cut must be performed whose cost is exactly equal to the length of that edge.

Thus, the minimum total cutting distance is equal to the sum of the lengths of all edges of the target polygon that do not lie entirely on one of the four boundary lines \(x=0\), \(x=n\), \(y=0\), or \(y=m\) of the rectangle.

The target polygon is given by its \(p\) vertices in order (either clockwise or counter-clockwise) and is guaranteed to be convex and completely contained within the rectangle. Note that some edges of the target polygon may lie on the boundary of the rectangle; these incur no cutting cost.

Given the rectangle dimensions and the target polygon, compute the minimum total cutting distance required so that, by performing successive cuts, the remaining part is exactly the target polygon. Output the answer as a floating‐point number with at least 6 decimal digits of precision.

The mathematical formulation for an edge between vertices \((x_i,y_i)\) and \((x_j,y_j)\) is: \[ \text{cost} = \begin{cases} 0, & \text{if }(x_i=x_j=0) \text{ or } (x_i=x_j=n) \text{ or } (y_i=y_j=0) \text{ or } (y_i=y_j=m),\\[6pt] \sqrt{(x_i-x_j)^2+(y_i-y_j)^2}, & \text{otherwise.} \end{cases} \] The answer is the sum of such edge costs over all edges of the polygon (taking the last vertex connected to the first vertex).

inputFormat

The first line contains three integers \(n\), \(m\), and \(p\) (with \(1\le n, m \le 10^9\) and \(3\le p\le 8\)).

The next \(p\) lines each contain two integers \(x_i\) and \(y_i\), representing the coordinates of the vertices of the target convex polygon given in order. It is guaranteed that \(0\le x_i\le n\) and \(0\le y_i\le m\) for all \(i\), and that the polygon is convex.

outputFormat

Output a single floating-point number — the minimum total length of the cut lines required to obtain the target polygon. The answer must be printed with at least 6 digits after the decimal point.

sample

10 8 4
0 0
10 0
10 8
0 8

0.000000