1001. A. Signal

题目描述

A 国和 B 国正在交战，战场是平面内的一个凸多边形 (P)。A 国的通信系统由 (n) 个频道组成。频道 (i) 由平面内两个不同的点 (A_i,B_i) 确定，其单位面积使用费用为 (w_i)。

战场内一点 (p) 能接收到频道 (i) 的信号，当且仅当

$$\overrightarrow{A_iB_i}\times\overrightarrow{A_ip}\geq0,$$

即 (p) 位于有向直线 (A_iB_i) 的左侧或直线上。

一次通信会恰好开启集合 (S) 中的所有频道。对于每个位置 (p)，收集所有满足

$$i\in S,\qquad \overrightarrow{A_iB_i}\times\overrightarrow{A_ip}\geq0$$

的费用 (w_i)，并将它们从大到小排列。若其中至少有 (k) 个数，则 (f_{S,k}(p)) 是第 (k) 个数；否则定义 (f_{S,k}(p)=0)。相同费用的不同频道需要分别计数。

A 国领导人想知道这次通信在整个战场上的总费用，即

$$\operatorname{Ans}(S,k) = \int_{p\in P}f_{S,k}(p)\,\mathrm dA.$$

现在有 (q) 次相互独立的询问。每次询问给出集合 (S) 和整数 (k)，求出对应的 (\operatorname{Ans}(S,k))。

样例解释

频道 (1) 可以在 (x\leq2) 的位置使用，频道 (2) 可以在 (y\geq2) 的位置使用，单位面积使用费用分别为 (3) 和 (5)。

对于第一组询问，(s=3)，两个频道均被开启，且 (k=1)。正方形左上、左下、右上三个面积均为 (4) 的区域所取最大费用依次为 (5,3,5)，所以答案为

$$4\times5+4\times3+4\times5=52.$$

第二组询问的 (k=2)。只有左上区域能同时接收到两个频道，其中第二大费用为 (3)，因此答案为 (4\times3=12)。

数据范围

• (1\leq T\leq5)；
• (1\leq n\leq18)；
• (3\leq m\leq30)；
• (1\leq q\leq2\times10^5)；
• 所有测试数据的 (n) 之和不超过 (36)；
• 所有测试数据的 (q) 之和不超过 (4\times10^5)；
• 所有坐标均为整数，绝对值不超过 (10^3)；
• 对每个频道均有 (A_i\neq B_i)；
• (1\leq w_i\leq10^6)；
• (0\leq s<2^n)，(1\leq k\leq n)；
• (P) 是严格凸多边形，顶点按照逆时针顺序给出。

为了尽可能避免浮点数误差，数据还满足以下性质：将凸多边形的边界直线和所有半平面边界直线放在一起考虑，

• 任意两条边界直线要么平行，要么夹角正弦的绝对值至少为 (10^{-3})；
• 平行的两条边界直线不会重合；
• 任意两条不平行边界直线的交点，到其他任意边界直线的距离至少为 (10^{-4})。
• 答案**绝对误差或相对误差不超过 $10^{-5}$**则正确。

输入格式

输入包含多组测试数据。第一行包含一个整数 (T)，表示测试数据组数。

对于每组测试数据：

• 第一行包含三个整数 (n,m,q)；
• 接下来 (m) 行，第 (i) 行包含两个整数 (x_i,y_i)，表示凸多边形的第 (i) 个顶点。顶点按照逆时针顺序给出；
• 接下来 (n) 行，第 (i) 行包含五个整数 (x_{i,1},y_{i,1},x_{i,2},y_{i,2},w_i)，表示 (A_i=(x_{i,1},y_{i,1}))、(B_i=(x_{i,2},y_{i,2})) 以及频道 (i) 的单位面积使用费用；
• 接下来 (q) 行，每行包含两个整数 (s,k)，表示一次询问。集合 (S) 使用十进制整数 (s) 编码：频道 (i) 属于 (S)，当且仅当 (s) 的第 (i-1) 个二进制位为 (1)。允许 (k>|S|)，此时答案为 (0)。

输出格式

对于每次询问，输出一行一个实数，表示对应通信的总费用。

设你的输出为 (x)，标准答案为 (y)。

样例输入

1
2 4 6
0 0
4 0
4 4
0 4
2 0 2 4 3
0 2 4 2 5
3 1
3 2
1 1
2 1
0 1
1 2

样例输出

52.0000000000
12.0000000000
24.0000000000
40.0000000000
0.0000000000
0.0000000000

来源：2026杭电多校-测试专用（成都七中） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1232&pid=1001 ⚠ 本题为 Special Judge。官方数据中的 .out 多为评测机判定输出（如 AC/OK/Correct/yes），导入后需自行提供 checker 方可正确评测。