P8130 [ICPC 2020 WF] Domes

ICPC2020 WF C

圣瓦西里大教堂是莫斯科乃至全俄罗斯最著名的地标。这座教堂建于 16 世纪伊凡雷帝时期，以其色彩斑斓的圆顶而闻名。到访这座城市时，如果不在红场拍摄这座前教堂的照片，旅程就不算完整。 莫斯科旅游局（MTB）希望游客能够尽可能安全地拍摄到教堂的完美照片。根据拍摄时所站的位置，圆顶的相对位置会有所不同（见图 C.1）。MTB 担心对于某些期望的圆顶排列，红场中可以拍摄到这种照片的区域会非常小，导致摄影师过度拥挤。为了避免可能导致的推搡、受伤以及新冠病毒传播，MTB 希望找到可以拍摄到任何期望圆顶排列的区域面积。 为了简化问题，假设相机具有 180 度的视角。作为说明，考虑图 C.2，其中显示了圆顶（标记为 1 到 5）和摄影师（绿色点）在平面上的位置。如果摄影师将相机直接对准左侧（直接对准圆顶 5）拍摄照片，则阴影区域内的所有内容都将在照片中可见。注意，在这张照片中，圆顶从左到右的顺序为 4, 3, 5, 2, 1。 给定红场内圆顶的位置以及照片中期望的圆顶从左到右的顺序，MTB 想知道在红场内可以拍摄到这种照片的区域面积。可以假设圆顶是点，因此除非在摄影师视角中成一条直线，否则它们不会相互遮挡。

输入的第一行包含三个整数 $d_x$、$d_y$ 和 $n$，其中 $d_x$ 和 $d_y$ $(2 \leq d_x, d_y \leq 10^5)$ 是红场的尺寸，$n$ $(1 \leq n \leq 100)$ 是圆顶的数量。红场的左下角位于原点 $(0,0)$，右上角位于坐标 $(d_x,d_y)$。 接下来的 $n$ 行中的每一行包含两个整数 $x_i$ 和 $y_i$ $(0 < x_i < d_x, 0 < y_i < d_y)$，给出圆顶的位置 $(x_i, y_i)$。第 $i$ 行描述了第 $i$ 个圆顶。没有两个圆顶位于同一位置。 最后一行包含数字 $\{1, \ldots, n\}$ 的一个排列，指定照片中圆顶从左到右的期望顺序。

输出红场内可以拍摄到圆顶按请求顺序排列的照片的区域面积。注意，如果没有位置可以拍摄到请求的照片，则面积可能为 $0$。你的答案的绝对误差或相对误差应不超过 $10^{-3}$。

题面翻译由 ChatGPT-4o 提供。