Perfect Shot of the Domes

The Moscow Tourism Board wants to ensure that photography of Saint Basil's Cathedral is both safe and yields the perfect shot. The cathedral has several domes whose relative positions change depending on where the photographer stands. In this problem the Red Square is modeled as an axis‐aligned rectangle and the domes are represented by points in the plane. Given the positions of the domes and a desired ordering from left to right, your task is to determine the area (within the square) from which a photographer can take a photo such that, after choosing an optimal orientation for a camera with a 180° field of view, the domes appear in the given left‐to‐right order.

More formally, assume the photographer can choose an arbitrary half‐plane (with the boundary line passing through his position) as his field of view. Let the domes be denoted by points D₁, D₂, …, D_n and let a desired permutation π[1..n] (where each π[i] is an index between 1 and n) be given. For any two domes A and B corresponding to π[i] and π[j] with i<j, it is a necessary and sufficient condition that the photographer’s position p satisfies \[ (A_y-B_y)\,p_x + (B_x-A_x)\,p_y \ge A_yB_x - A_xB_y \] (in other words, when vectors \(\vec{pA}\) and \(\vec{pB}\) are compared, the one pointing to dome A appears to the left of B). The overall feasible region is the intersection of these half-planes (for every pair π[i] and π[j] with i<j) together with the rectangular region representing Red Square. Your task is to compute the area of this region.

You may assume that the dome positions are in general position (no three points are collinear with any photographer's position on a boundary line) and that n is small so that an algorithm based on iterative half-plane intersection will run efficiently.

Note: All formulas are rendered here in LaTeX.

inputFormat

The input begins with a line containing four real numbers x_min y_min x_max y_max representing the coordinates of the bottom‐left and top‐right corners of Red Square. The next line contains a positive integer n (2 ≤ n ≤ 10), the number of domes. The following n lines each contain two real numbers representing the coordinates of a dome. Finally, the last line contains a permutation of the integers from 1 to n (separated by spaces), which is the desired left-to-right ordering of the domes in the photograph.

outputFormat

Output a single real number representing the area of the region within Red Square from which a photographer can achieve the desired ordering. The answer should be printed with at least 6 digits after the decimal point if necessary.

sample

0 0 10 10
2
2 2
8 2
1 2

80.000000