凸包优化（Convex Hull Trick, CHT） 问题

https://dmoj.ca/problem/dmopc15c2p5

题意可以抽象为：给定 $N$ 条直线 $y_i = v_i \cdot x + s_i$，其中 $x$ 代表天数，$v_i$ 是斜率，$s_i$ 是截距。对于每个询问 $d$，我们需要找到在 $x=d$ 时 $y$ 值最大的那条直线。如果有多个最大值，选择编号最小的那条。

由于 $N$ 和 $Q$ 都在 $10^5$ 级别，暴力遍历每条直线会超时（$O(NQ)$）。我们需要维护这些直线的上凸壳（Upper Convex Hull）。

预处理阶段（O(N log N + D)）

• 按斜率 m 升序排序（相同 m 时 s 升序）。
• 用 while(top>=0 && st[top].m==line[i].m) top–; 只保留每个 m 下 最大的 s（因为同一斜率下 s 越大永远更优）。
• 用 check 函数维护上凸包（upper envelope），只保留可能成为最优的线段（hull 大小 ≤ 1000）。 check 是标准的叉积判断：当三条线 a-b-c 构成“右转”时弹出 b，保证凸性（严格 <，相等时不弹出，保留中间线以便后续处理多线共点）。

核心：线性扫描预计算所有答案（O(D) = O(5×10^5)）

• ans[1..500000] 数组提前算好每个 d 的最优 id。
• 遍历 j 从 1 到 maxX，同时维护当前 hull 上的线段 i。
• 计算两条相邻 hull 线 i 和 i+1 的交点：text(m_{i+1}−m_i)·j ? s_i−s_{i+1}
  • y1 < y2：j 仍在第 i 条线的支配区间 → 记录 st[i].id，j++
  • y1 == y2：精确相交点（tie）→ 取 min(id_i, id_{i+1}) 并 i++（重要！）
  • y1 > y2：已超过交点 → i++（切换到下一条线）
• 最后一段（i==top）直接用 for 填满剩余 j。

Tie 处理完美 当多条线（≥3）在同一个整数 d 精确相交时，因为凸包构建时不弹出共线中间线，扫描时会在同一个 j 上连续执行 == 分支，ans[j] 通过多次 min 操作自然得到所有共线线中 id 最小的那个，完全符合题目要求。