P16384 [IATI 2025] Soft Drinks

Peter 最近开始了一项兼职爱好——混合软饮料。他已经获得了对 $N$ 种不同饮料类型的无限量供应权限。每种第 $i$ 类饮料（$0 \leq i < N$）每升含有 $A_i$ 克糖和 $B_i$ 克酸。 Peter 正在家中举办一场聚会，并邀请了 $Q$ 位最亲密的朋友。每位朋友都十分注重健康且颇为挑剔，并带着以下约束前来： - $M_A$：他们愿意摄入的糖的最大总重量（以克计）。 - $M_B$：他们愿意摄入的酸的最大总重量（以克计）。 - $L_A$，$R_A$：他们只会饮用那些糖浓度（每升含糖克数）在 $[L_A, R_A]$ 范围内（含两端）的饮料类型。 Peter 可以将不同数量的每种饮料（包括分数数量）混合，以调制定制化的无酒精鸡尾酒。形式化地，令 **实数非负** 的 $V_i$ 表示在最终混合物中使用的第 $i$ 种饮料的量（以升计）。则： - 该无酒精鸡尾酒的总体积为 $\sum_{i=0}^{N-1} V_i$ 升。 - 混合物中糖的总重量为 $\sum_{i=0}^{N-1} V_i \times A_i$ 克。 - 混合物中酸的总重量为 $\sum_{i=0}^{N-1} V_i \times B_i$ 克。 你的任务是帮助 Peter 确定他能为每位朋友提供的 **最大总体积（以升计）**，同时满足他们各自的约束。 ### 实现细节 你需要实现如 $\texttt{soft\_drinks.h}$ 中所定义的以下函数： ```cpp void init(const std::vector& A, const std::vector& B); ``` $\verb|init|$ 函数将在任何其他查询之前被恰好调用一次。其参数对应如下： - $\texttt{A}$：一个长度为 $N$ 的向量，其中 $\texttt{A[i]}$ 是第 $i$ 种饮料每升的含糖量。 - $\texttt{B}$：一个长度为 $N$ 的向量，其中 $\texttt{B[i]}$ 是第 $i$ 种饮料每升的含酸量。 ```cpp double friendDrink(int Ma, int Mb, int La, int Ra); ``` $\verb|friendDrink|$ 函数会为 $Q$ 位朋友中的每一位各调用一次。其参数对应如下： - $\texttt{Ma}$：该朋友将摄入的糖的最大总重量。 - $\texttt{Mb}$：该朋友将摄入的酸的最大总重量。 - $\texttt{La}, \texttt{Ra}$：该朋友愿意接受饮用的饮料类型的糖浓度所在闭区间边界。 该函数应返回一个 $\texttt{double}$，表示 Peter 可以在不违反该朋友任何约束的情况下为其提供的最大体积（以升计）。 如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则被视为正确。即，若你的答案为 $a$，正确答案为 $b$，则当 $\frac{|a-b|}{\max(1, |b|)} \le 10^{-6}$ 时，你的答案会被接受。 ### 本地测试 提供了一个本地评测器 $\texttt{Lgrader.cpp}$ 以及相应的头文件 $\texttt{soft\_drinks.h}$。

输入格式： - 第一行：整数 $N$ 和 $Q$。 - 接下来的 $N$ 行：每行两个整数 $A_i$ 和 $B_i$，描述每种饮料。 - 接下来的 $Q$ 行：每行四个整数 $M_A$, $M_B$, $L_A$ 和 $R_A$，描述每位朋友。 评测器将调用 $\texttt{init}$，随后为每位朋友调用 $\texttt{friendDrink}$，并将结果打印至标准输出。

无

### 数据范围 - $1 \leq N, Q \leq 10^5$ - $0 \leq A_i, B_i, M_A, M_B, L_A, R_A \leq 10^9$ - 要么 $A_i \neq 0$ 要么 $B_i \neq 0$。 ### 子任务 | **子任务** | **分值** | **$N$** | **$Q$** | **附加约束** | | :---: | :---: | :---: | :---: | :---: | | $0$ | $0$ | $--$ | $--$ | 样例测试 | | $1$ | $6$ | $\leq 2$ | $\leq 100$ | $--$ | | $2$ | $9$ | $\leq 10^5$ | $\leq 10^5$ | $M_A = M_B$ | | $3$ | $7$ | $\leq 10^5$ | $\leq 10^5$ | $M_A = 0$, $A_i = 0$ | | $4$ | $9$ | $\leq 500$ | $\leq 500$ | $--$ | | $5$ | $15$ | $\leq 5000$ | $\leq 5000$ | $--$ | | $6$ | $7$ | $\leq 10^5$ | $\leq 1000$ | $(L_A, R_A) = (0, 10^9)$ | | $7$ | $18$ | $\leq 10^5$ | $\leq 10^5$ | $(L_A, R_A) = (0, 10^9)$ | | $8$ | $29$ | $\leq 10^5$ | $\leq 10^5$ | $--$ | 只有在成功通过某子任务的所有测试及其所包含的所有其他子任务的测试后，才能获得该子任务的分数。 翻译由 DeepSeek V4 Pro 完成