题目背景

ICPC2020 WF C

题目描述

Saint Basil's Cathedral is the best-known landmark of Moscow and maybe even of all of Russia. Built under Ivan the Terrible in the $16$$^{\text {th }}$ century, the cathedral is known for its colorful domes. No visit to the city is complete without taking a photo of the former church in Red Square.

The Moscow Tourism Board (MTB) wants to make it as safe as possible for tourists to take the perfect shot of the cathedral. Depending on where you stand when you take a picture, the relative positions of the domes will be different (see Figure C.1). The MTB is concerned that for some desired configurations of domes the region in Red Square where such a photo is possible will be so small as to lead to a dangerous overcrowding of photographers. Wanting to avoid the inevitable pushing, shoving, injury, and Covid that this could cause, the MTB would like to find the area of the region where a photo is possible for any desired ordering of the domes.

For simplicity, assume that cameras have a $180$-degree viewing angle. As an illustration consider Figure C.2, which shows the location of the domes (labeled $1$$\sim$$5$) and the photographer (green dot) in the plane. If the photographer shoots a picture aiming the camera straight towards the left (directly at dome $5$), then everything in the shaded area will be visible in the photograph. Note that in this photograph, the domes will appear in order $4, 3, 5, 2, 1$ from the left to the right.

Given the location of the domes within Red Square and a desired left-to-right order of the domes in the photograph, MTB wants to know the area of the region within Red Square from which such a photograph can be taken. You can assume that the domes are points, so that they do not block each other unless they are in a straight line from the photographer's view.

输入格式

The first line of input contains three integers $d_x$, $d_y$, and $n$, where $d_x$ and $d_y$ $(2 \leq d_x, d_y \leq 10^5)$ are the dimensions of Red Square, and $n$ $(1 \leq n \leq 100)$ is the number of domes. The bottom-left corner of Red Square is at the origin $(0,0)$ and the top-right corner is at coordinate $(d_x,d_y)$.

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ $(0 < x_i < d_x, 0 < y_i < d_y)$, giving the locations $(x_i, y_i)$ of the domes. The $i^{\text {th }}$ line describes dome number $i$. No two domes are in the same location.

The last line contains a permutation of the numbers $\{1, \ldots, n\}$ specifying the desired left-to-right viewing order of the domes in the picture.

输出格式

Output the area of the region within Red Square from which one can take a photo that shows the domes in the requested order. Note that the area may be $0$ if there is no position from which to take the requested photo. Your answer should have an absolute or relative error of at most $10^{-3}$.

题目大意

对于图 C.2（样例 $1$ 解释）： 绿点为摄影师，相机视角为 $180$ 度，黑点为圆顶，规定从左到右依次为 $4, 3, 5, 2, 1$，蓝色区域为能拍摄到的部分，假设所有圆顶均为一个点，即不会互相遮挡，除非圆顶与摄影师位于同一直线上。

简要题意： 给定一张长为 $d_x$， 宽为 $d_y$，有 $n$ 个点的地图，设地图左下角坐标为 $(0, 0)$，右上角坐标为 $(d_x, d_y)$；给出 $n$ 个点的坐标 $(x_i, y_i)$（依次为 $1$ 到 $n$），保证任意两点不重合；最后一行给出要求拍摄出的圆顶顺序（从左到右）。输出所有符合要求的摄影师站位点的集合图形的面积，若不存在则输出 $0$。答案的相对或绝对误差不能超过 $10^{-3}$。

对于全部数据，$2 \le d_x, d_y \le 10^5$，$1 \le n \le 100$，$0 < x_i <d_x$，$0 < y_i <d_y$。

100 100 5
30 70
50 60
50 40
30 30
20 50
4 3 5 2 1

450.000000

100 100 5
30 70
50 60
50 40
30 30
20 50
1 2 5 4 3

0.000000