第一次在 vjudge 上刷到 UVa 1115 Water Shortage 的时候我第一反应是这题目里应该藏着一堆管道和水流模拟结果题面读下来才发现它其实是把“往容器里倒水”这件事干净利落地转化成了一个二分答案问题。考点非常聚焦一个容器剖面多边形给定目标水量或者一个面积比例求最终水位的高度。这道题很适合两类人看一类是刚学完二分模板想找点真实应用场景练手的另一类是准备 ICPC 或者区域赛想顺手把计算几何的基础面积操作补齐的。我自己在这道题上折腾了大半个晚上中间换过两种面积求法踩过 EPS 的坑也踩过裁剪算法的坑最后整理成这篇笔记希望能帮你少走点弯路。1. 这道题到底在让我们求什么从题目名到二分模型1.1 题意还原一个容器剖面一个目标水量UVa 1115 的题面在不同来源的题库里措辞略有出入但我按自己处理时的版本描述一下核心你会拿到一个简单多边形的顶点坐标这个多边形代表一个容器的纵向剖面顶点按顺时针或者逆时针顺序给出。题目会给你一个目标值可能是水的体积也可能是某个分割比例要求你求出一条水平线的 y 坐标这条线以下的多边形截面积恰好等于目标值。说白了就是要你解方程areaBelow(h) target其中areaBelow(h)是容器剖面在高度 h 以下的部分的面积。注意这里用的是“面积”而不是“体积”因为题目给的多边形剖面通常默认宽度为 1面积和体积在数值上统一。理解到这一层这道题就从“几何题”变成了“函数求根题”。有些版本会给比例 P:Q要求把多边形面积按这个比例切开那 target 就是总面积乘以 P/(PQ)本质上没有任何区别。所以第一步永远是先搞清楚 target 到底是什么别上来就二分。1.2 单调性为什么水位高水量就一定多二分能成立的前提是areaBelow(h)关于 h 单调不减。这一点听起来像废话但值得认真想一下因为很多人在写的时候并没有真正意识到自己依赖了这个性质。想象一个形状奇怪的杯子比如一个底下宽、上面窄的花瓶。你往里面倒水水位每上升一毫米新增的水量可能不一样在瓶身宽的地方水位上升一毫米需要很多水在瓶口窄的地方只需要一点点。但是无论多还是少新增的水量不会是负数。也就是说水位从 0 升到 H 的过程中水面以下覆盖的面积只会变多不会变少。这正是单调性。从几何角度看areaBelow(h)的增量可以理解为水平线 yh 从下往上扫过时新增的那一条“窄带”的面积。只要多边形是简单多边形水能正常填充不会出现倒着倒着水面上升但水量反而减少的情况。所以这个东西可以直接二分水位低水量少水位高水量多。单调性满足二分就是安全的。1.3 上下界如何选别让二分跑出容器二分区间选得好不好直接影响代码的健壮性。我一开始偷懒直接把下界设成 0上界设成一个很大的数结果样例过了换个数据就 WA。后来才发现问题出在边界情况上。正确的做法是先遍历所有顶点取 y 坐标的最小值作为二分下界 lo最大值作为上界 hi。为什么不能直接用 0因为容器可能整体悬浮在坐标系的某个地方比如顶点纵坐标从 100 到 200你从 0 开始二分前面一大半区间对应的面积都是 0白白浪费迭代次数。更关键的是如果目标水量小于等于 0你从 0 二分下去最后会得到一个“非法”的水位而不是直接输出最低点。我习惯在二分之前先算一遍容器总面积然后加两个特判如果目标水量极小接近 0或者小于 0直接输出 lo如果目标水量接近总面积或者大于总面积直接输出 hi。这样处理有两个好处一是避免二分在边界处产生浮点误差二是让主二分循环始终处理“target 严格在合法范围内”的情况逻辑更清晰。如果题目保证 target 一定在范围内这两个特判不写也能过但写上更稳妥反正就两行代码。2. 面积函数实现WA 重灾区我为什么选了裁剪加鞋带2.1 完整面积先垫底鞋带公式areaBelow(h)是整道题的核心也是绝大多数 WA 的根源。在实现它之前得先保证自己能把一个完整多边形的面积算对。这里最常用的是鞋带公式Shoelace FormulaS 0.5 * |Σ (x_i * y_{i1} - x_{i1} * y_i)|原理不复杂它本质上是格林公式的一个离散版本把多边形面积分解成每条边对坐标原点的“有向三角形”面积之和。因为多边形是闭合的中间部分会被抵消最后只剩下外轮廓的面积。代码很简单struct Point { double x, y; }; double polygonArea(const vectorPoint poly) { double res 0.0; int n poly.size(); for (int i 0; i n; i) { int j (i 1) % n; res poly[i].x * poly[j].y - poly[j].x * poly[i].y; } return fabs(res) * 0.5; }注意这里取了绝对值因为顶点可能是顺时针也可能是逆时针。如果你不取绝对值后面areaBelow和总面积比较的时候可能莫名其妙差一个符号到时候查都查不出来。2.2 水平线以下面积半平面裁剪加鞋带要求areaBelow(h)最直观的思考方式是把多边形用水平线 yh 切一刀保留下半部分形成一个新多边形然后用上面的鞋带公式求这个新多边形的面积。这个操作在计算几何里叫“半平面裁剪”。最经典的是 Sutherland-Hodgman 算法虽然名字听起来高级但实现很短核心逻辑就是遍历多边形的每一条边判断边的两个端点相对于切割线的位置。我来写一个裁剪版本的实现直接可用Point intersect(const Point a, const Point b, double h) { double t (h - a.y) / (b.y - a.y); return {a.x t * (b.x - a.x), h}; } vectorPoint clipBelow(const vectorPoint poly, double h) { vectorPoint res; int n poly.size(); for (int i 0; i n; i) { Point cur poly[i]; Point nxt poly[(i 1) % n]; bool curIn cur.y h 1e-9; bool nxtIn nxt.y h 1e-9; if (curIn) res.push_back(cur); if (curIn ! nxtIn) { res.push_back(intersect(cur, nxt, h)); } } return res; } double areaBelow(const vectorPoint poly, double h) { vectorPoint clipped clipBelow(poly, h); if (clipped.size() 3) return 0.0; return polygonArea(clipped); }这个实现的逻辑可以拆成四种情况当前端点在上方下一个端点在下方当前端点不加入但把交点加入。下一轮循环时下一个端点作为“当前端点”会被加入所以交点只出现一次多边形闭合正确。当前端点在下方下一个端点在上方当前端点加入交点加入下一个端点不加入。两个都在下方当前端点加入下一个端点下一轮加入。两个都在上方什么都不加。我一开始写这个函数的时候很容易在“当前端点在上方、下一个端点在下方”这种分支里多 push 一个点或者少 push 一个点导致裁剪出来的多边形顶点顺序错乱。解决办法是不要凭记忆写而是每一轮都问自己三个问题当前点要不要交点要不要什么时候要想清楚再写。2.3 为什么不用逐边梯形积分容易漏细节我在第一次做这道题的时候并没有直接上裁剪而是用了一个看起来很聪明的办法对每条边单独积分把每条边在 yh 以下的部分累加起来。这个思路理论上是正确的但实现起来坑非常多。具体来说你需要对每条边求出它和 yh 的交点然后判断哪一段在下方再对这一段做梯形积分。逻辑分支有五六种两个端点都在下方、两个都在上方、一个上一个下、边是水平线且恰好等于 h、边是垂直边……每一种都要小心。我写完以后自以为万无一失结果交上去 WA 了好几发。后来调试发现问题出在水平边当一条边恰好就是 yh 的一部分时我把它算了两遍。这种边在实际样例里确实可能出现而裁剪算法的好处是它天然帮你处理了这种情况——水平边正好在切割线上时相关顶点会被加入裁剪结果但鞋带公式对共线点、重复点并不敏感不会产生额外面积。所以我的结论是求水平线以下的多边形面积直接用“裁剪 鞋带”别整那些花活。代码短分支少出问题的概率低。如果你坚持用梯形积分请务必做好水平边和顶点恰好落在切割线上的测试否则调一晚上都不奇怪。下表是这两种方案的对比方案代码量出错点推荐度裁剪 鞋带短裁剪分支容易 push 错点高逐边梯形积分较长水平边重复计算、符号处理低3. 二分循环里的三个魔鬼细节EPS、迭代次数、边界点3.1 EPS 设多少太小没意义太大直接 WA写比较逻辑的时候cur.y h这种判断必须带 EPS不然当水位刚好等于某个顶点的 y 坐标时那个顶点会被判到切割线以上面积函数会突然少掉一整块。EPS 设多少合适我见过有人设 1e-3结果在精度要求高的题目上直接 WA有人设 1e-12结果 double 运算自身误差都比这个大。我一般设 1e-9在绝大多数题目里都够用。如果你不确定可以把 EPS 放到 1e-8 到 1e-10 之间再结合固定迭代次数来保证整体精度。3.2 固定迭代次数比 while (hi - lo EPS) 更安心很多二分模板长这样while (hi - lo 1e-7) { double mid (lo hi) / 2; ... }这个写法本身没错但有两个隐患。第一如果初始区间长度很大比如 1e6而 EPS 设成 1e-9那需要迭代大约 50 次才能进入循环条件但你要知道 double 的精度只有大约 15 位有效数字到了区间长度 1e-9 量级hi - lo的计算本身已经开始抖动循环可能会提前结束也可能迟迟不结束。第二如果 EPS 设得太大比如 1e-4而题目要求输出精确到 1e-2那可能循环结束得太早答案误差没控制住。所以我更推荐固定迭代次数double lo minY, hi maxY; for (int it 0; it 60; it) { double mid (lo hi) / 2.0; if (areaBelow(poly, mid) target) lo mid; else hi mid; } printf(%.2f\n, hi);为什么是 60假设初始区间长度是 1e4二分 60 次以后区间长度是 1e4 / 2^60这个数远小于 double 能表示的最小精度再循环已经没有意义。固定迭代次数的好处是你永远不用担心死循环也不用纠结 EPS 设多少。输出的时候保留几位小数完全取决于题目要求我一般先保留 2 位如果样例没过再改成更高精度。3.3 顶点恰好落在切割线上裁剪算法的重复点问题前面提到裁剪算法在遇到顶点 y 恰好等于 h 时会出现一些特殊情况。举个例子多边形的两个顶点 A、BA 在下方B 的 y 恰好等于 h。按照我的裁剪代码curIn为 true因为带了 EPSnxtIn也为 true所以 A 和 B 都会加入结果。如果下一条边是 B 到 C 且 C 在上方那 B 会再次被判断为“在下方”同时 B 到 C 的边会算出一个交点而这个交点恰好就是 B 自己。结果就是裁剪后的多边形里出现两个坐标完全相同的点。这会不会导致面积算错不会。因为鞋带公式里长度为 0 的边贡献为 0重复点只是多了一次 xy-xy 的计算不影响结果。真正要注意的是polygonArea函数里如果遇到重复点不要去做额外的“去重”操作因为去重可能破坏顶点顺序。如果你的实现里出现了裁剪后不足 3 个点的情况比如多边形整体在切割线以上clipped可能是空的也可能是退化的线段。这时候面积函数应该直接返回 0否则鞋带公式会返回一个看起来莫名其妙的数。4. 从 Water Shortage 延伸开这套二分几何题的变体与迁移4.1 变体一多个水槽同时注水Water Shortage本身只有单个容器剖面但我见过很多类似的题改成给你若干个矩形水槽每个水槽的底部高度、宽度不同然后给定总水量求最终水位。这种题的套路完全一样二分水位 h计算所有水槽在 h 以下的面积之和。每个矩形水槽的贡献是width * max(0, min(height, h - bottom))写一个总的totalAreaBelow(h)函数把所有水槽的面积累加再和总水量比较。由于每个水槽的贡献随 h 单调不减总和也单调不减二分依然成立。这里有个坑不同水槽的底部高度不同h 低于某个水槽的底部时那个水槽的贡献是 0不能算成负数。我之前见过有人直接在h - bottom上取绝对值那结果整个就乱套了。4.2 变体二按比例切分多边形面积题目不给你水量给你一个比例 P:Q要求找一条水平线把多边形面积分成 P 和 Q 两部分。这个比直接给水量还简单target totalArea * P / (P Q)然后二分 h让areaBelow(h)等于这个 target。唯一要注意的是题目可能要求输出上面部分和下面部分的面积比也可能要求输出线的位置读题的时候要看清。我做这道题的时候还在想另一种做法如果比例中的 P 是“上半部分”的比例那 target 是总面积乘以 P 还是 Q这种东西特别容易搞混。我建议先画一个简单的矩形用例比如宽 2 高 1 的矩形总面积是 2如果 P1、Q3那切割线应该在 y0.5 处。用这种小用例验证自己的 target 公式比对着题面猜半天效率高得多。4.3 变体三斜线切割而不是水平线有些题不切水平线而是给一条有斜率的直线比如y kx b要求调整 b 让直线两侧的面积满足某个比例。这种题的本质和水平线版本没有任何区别还是二分参数 b然后求多边形在直线以下部分的面积。只是面积函数的实现会更复杂一点。裁剪的半平面从“y h”变成了y kx b你需要在每条边上求出与这条斜线的交点然后保留在斜线下方的顶点。裁剪算法本身不用换只是curIn的判断条件变成了cur.y k * cur.x b EPS。我第一次遇到这种题时下意识觉得要重新发明一套几何工具后来意识到 Sutherland-Hodgman 裁剪完全通用只是把“半平面”的表达式换掉而已。所以如果你想举一反三最好把裁剪函数写成一个通用的“多边形与半平面的交集”形式而不是硬编码y h。我建议这样封装double f(Point p) { return p.y - (k * p.x b); // 0 表示在多边形下方 } bool inside(Point p) { return f(p) EPS; }面积函数里所有判断都改成调用inside这样从水平线切到斜线只改一行函数体其他全都不用动。4.4 我刷这道题时踩过的坑与调试习惯最后分享几个我自己调试时踩出来的经验。第一个二分循环内部打印areaBelow(mid)。如果你发现这个值在某个区间内不单调那不是二分写错了而是面积函数写错了。我在第一次写梯形积分版本时就遇到了这种“曲线回落”的现象打印出来一看水平边被重复计算了面积在某个点突然跳变。用裁剪 鞋带之后这个问题彻底消失。第二个面积函数写好后先单独测试几个简单图形再进二分。我习惯用的测试图形是一个矩形、一个三角形、一个 L 形。矩形用来测普通情况三角形用来测顶点恰好落在切割线上的情况比如切割线在某个顶点高度L 形用来测多边形非凸的情况。这三个图形都过了再去跑样例基本不会出问题。第三个输出精度。UVa 的老题目经常要求小数点后保留几位我一开始用printf(%.2f\n, hi)后来发现有的题面要求 3 位小数有的是 4 位。WA 不一定是算法错了也可能只是输出格式不对。建议先看一下输出样例的格式尤其是末尾有没有多余空格、小数点后几位再决定输出格式。第四个坐标读入用 double不要用 int。题目给的坐标可能都是整数但在交点计算里t (h - a.y) / (b.y - a.y)会产生小数如果你一开始把坐标存成 int后续全是整数除法结果直接变成 0然后整个面积函数就废了。我后来越做越顺手主要是因为这题让我建立了“二分答案 几何面积”的固定套路先把问题抽象成单调函数求根再把函数实现得简单可靠最后用固定迭代次数来控制精度。三步走下来不管是单容器、多水槽还是斜线切割都能在几分钟之内套用上去。最后再提醒一句如果你交上去 WA别急着改二分先去打印面积函数的值90% 的问题都出在里面。