信奥题解：P5867 Fishermen，几何转区间覆盖的实战细节

这周刷题打卡轮到第2946篇遇上的是P5867 [SEERC 2018] Fishermen。坦白讲我第一次读完题面就把它当成了一道几何题坐标系、渔夫、鱼竿长度脑子里全是点到直线距离、圆的相交之类的模板。可真要下手写C的时候才发现它绕开了一堆几何模板真正考的只有一个“由几何到区间覆盖”的转化再加一点前缀和的思想。这篇不打算写成一篇标准的“题解式流水账”我想按自己从读题到AC的完整思考顺序来写。你会发现这题代码量不大五六十行就能过但中间那几步推导和精度处理恰恰是很多人在信奥实战里反复翻车的地方。无论你是刚开始刷普及组题还是已经在冲提高组的常数优化这篇应该都能给你一点启发。1. 题目到底在说什么站在x轴上的渔夫和一个圆先花点时间把题意和输入输出的结构说清楚因为这类区域赛题目通常描述很长但抽象完之后往往就剩一个很干净的问题。题目大意我用自己的话说一遍有一片湖湖面被放到一个平面直角坐标系里岸线就是x轴湖在x轴上方里面生活着n条鱼第i条鱼的坐标是(xi, yi)。然后有m个渔夫每个渔夫站在x轴上坐标为(ai, 0)。所有渔夫手里的鱼竿长度都一样统一是l。渔夫能钓到一条鱼当且仅当这条鱼到他的直线距离不超过鱼竿长度l。你要做的就是对于每个渔夫输出他能钓到的鱼的数量。输入格式一般是这样的第一行是三个整数 n、m、l分别表示鱼的数量、渔夫数量、鱼竿长度接下来n行每行两个整数xi、yi表示鱼的位置再接下来m行每行一个整数表示渔夫在x轴上的坐标。数据规模方面n和m通常可以到2e5这个级别坐标和l的绝对值也可能到1e9。这个规模基本上就是在告诉你暴力枚举渔夫和鱼的组合复杂度O(n*m)是绝对跑不完的。还有一个特别容易踩的误读有些朋友看到坐标系里的距离下意识以为是曼哈顿距离也就是|x1-x2| |y1-y2|。但这道题明确说的是“鱼竿长度”钓鱼竿在物理世界里是一根直杆所以这里用的是欧氏距离也就是sqrt((x1-x2)^2 (y1-y2)^2)。这个区别非常重要因为它直接决定了后面能不能做那个关键的数学化简。如果题目改成曼哈顿距离那整个推导都要换一种玩法。简单举个例子验证距离定义假设鱼竿长度l5有一条鱼在(0, 3)渔夫站在(4, 0)。欧氏距离是sqrt(4^2 (-3)^2) 5刚好能钓到如果按曼哈顿距离算就是7反而钓不到。所以一开始就得把模型定死渔夫能钓到鱼等价于不等式(x-a)^2 y^2 ≤ l^2成立其中a是渔夫的x坐标。理解了这一点你会发现这题的本质根本不是几何计算而是一个“一个点能被多少个区间覆盖”的统计问题。下面这节就来推这个核心转化。2. 从“圆”到“区间”这道题真正的题眼所在现在我们把渔夫设成(a, 0)鱼设成(x, y)。前面说了能钓到的条件是(x - a)^2 y^2 ≤ l^2稍微整理一下把a单独放到一边(x - a)^2 ≤ l^2 - y^2这个不等式能不能继续解取决于右边的l^2 - y^2是否非负。如果y l也就是鱼离x轴的距离已经大于鱼竿长度那么l^2 - y^2是负数平方数不可能小于负数所以这条鱼永远不可能被任何渔夫钓到。这类鱼可以直接扔掉后续不用管了。当y ≤ l时我们可以令d floor(sqrt(l^2 - y^2))这里d是一个整数表示在x轴方向上渔夫和鱼之间允许的最大水平距离。因为渔夫坐标是整数所以只要a落在[x-d, xd]这个闭区间内就一定满足上面那个不等式。反过来如果a不落在这个区间里那么|x-a| d于是(x-a)^2 y^2 l^2肯定钓不到。这一步的意义怎么强调都不过分它把“平面上的圆形区域”转换成了一条直线上的闭区间。每个渔夫就是数轴上的一个点每条鱼贡献一个能覆盖若干点的区间题目变成了“统计每个点被多少个区间覆盖”。我当初看到这题时第一反应是用点到直线的距离公式算垂足然后判断渔夫是否在某个范围内。后来发现完全没必要直接对横坐标做区间覆盖统计就行。因为渔夫全站在x轴上相当于所有鱼到x轴的垂直距离是固定的y于是二维距离约束退化成了一维的 |x-a| 约束。这就是出题人把“岸线”放在x轴上的原因——它故意让你能用这种方式降维。这个转化还会带来一个额外好处所有渔夫的坐标是整数所以d哪怕是通过浮点开方算出来的最终也只要取整数下界就能保证答案正确。换句话说只要d的整数值算对了就不存在“区间的某个端点恰好卡在浮点边界导致渔夫点被漏算”的问题。但这里埋了一个精度大坑第四节会重点展开。从竞赛教学的角度看这道题的“题眼”就是这种降维思维。很多几何题看着需要计算几何模板实际上只要坐标系里有大量特殊位置比如所有点都在一条直线上就能通过代数变形转成更简单的数据结构问题。P5867把这个思想考得非常直白所以它才适合放进信奥刷题序列里反复品味。3. 三种实现思路的对比暴力、差分扫描和优先队列转化完成之后问题就变得很“模板”了。给你n个区间m个单点查询求每个点被多少个区间覆盖。这个子问题有不止一种做法我实际思考和测试了三种这里把它们的取舍讲清楚。3.1 暴力枚举为什么必挂最直观的想法对于每个渔夫遍历所有鱼逐一判断是否在区间内。复杂度O(n*m)。n和m如果都是2e5那就是4e10次操作哪怕C单次循环再快跑完也要几十秒到几分钟TLE是板上钉钉的。所以别浪费时间在暴力上暴力唯一的价值是后面写对拍程序验证正解时用。3.2 事件差分扫描我最推荐的做法这个方法本质上就是“扫描线”思想。对于一个闭区间[x-d, xd]我们把它拆成两个事件在坐标x-d处覆盖数加1在坐标xd1处覆盖数减1。把所有事件按坐标从小到大排序再把渔夫的坐标也从小到大排序。然后维护一个cur变量从左到右扫描渔夫坐标遇到一个坐标p就先把所有x ≤ p的事件依次加到cur里。到处理完这些事件之后cur的值就是在坐标p这个点上生效的区间数量也就是这个渔夫能钓到的鱼数。为什么这个做法正确因为“覆盖数”是一个累加量区间的左端点代表它开始覆盖后续的点区间的右端点1代表它离开覆盖范围。我们每移动到一个新的查询点就把所有已经开始的覆盖加上、所有已经结束的覆盖减掉cur天然就是当前点的覆盖数。事件数组的总量是2n排序加扫描的总复杂度是O(n log n m log m)几乎可以跑满2e5的数据规模。这个方案代码最短思路也最清晰。我最后AC用的就是它。3.3 左端点排序配合优先队列另一种常见做法是把所有区间按左端点从小到大排序然后遍历排序好的渔夫坐标p把所有左端点 ≤ p的区间加入一个小顶堆堆里存的是右端点之后弹出所有右端点 p的区间此时堆里剩下的区间数量就是答案。这个方法本质上也是扫描线但它不是用“事件1 / -1”的差分方式维护cur而是动态维护“当前还活着的区间集合”。代码会比事件差分长一点需要多写一个优先队列的比较逻辑但理解起来更直观特别适合第一次接触区间覆盖计数的朋友。两种方法复杂度一样我个人更推荐事件差分因为它不需要额外的堆结构也就少了很多边界情况。不过如果你觉得优先队列那套更顺手比赛时用自己最熟的做法就行没必要强行换。3.4 离散化加前缀和的本质有人可能会想到“把所有坐标离散化然后开一个差分数组最后跑前缀和”。这个思路和事件差分本质上是同一个东西区别只在于实现方式。事件差分直接对事件排序在扫描渔夫时临时累加离散化加前缀和则是把事件和渔夫坐标全部揉进一个坐标数组统一去重、统一差分、统一求前缀和。两种写法在本题都能过但事件差分的优点是不用刻意处理“xd1这个坐标不在任何渔夫坐标集合里”的情况。离散化如果漏了这个点拆出来的-1事件会找不到落点反而容易写错。所以从实战角度我用事件差分作为标准解。4. 真正容易翻车的细节整数开方和浮点精度如果到这里就兴冲冲去写代码大概率会在“求d”这一步翻车。这也是P5867这道题在洛谷评论区里讨论最多的地方。4.1 double开方的精度问题如果直接写int d sqrt(l*l - y*y)在数据很大的时候几乎必错。原因有两个层面第一l和y都可能到1e9ll - yy会是一个接近1e18的整数。double的尾数只有53位二进制精度换算成十进制大约是16位有效数字根本不可能精确表示1e18这个量级的整数。误差可能达到几十甚至几百开方之后传给int截断结果自然不可信。第二就算数字很小比如l^2 - y^2 16理论上sqrt(16.0)应该精确等于4.0但某些C编译环境和硬件上浮点实现可能返回3.9999999999999996这样的值。直接转int就变成了3区间端点整体错1答案直接WA。我当初就吃过这个亏。后来做了一组很小的随机数据对拍才发现差1的地方全是浮点交互误差导致的。4.2 安全的整数开方写法既然浮点不可靠那就用整数逻辑来算d。最稳妥的写法是先估算一个近似值再用加减法修正到正确结果long long sqrt_floor(long long x) { long long r sqrt((long double)x); while ((r 1) * (r 1) x) r; while (r * r x) --r; return r; }这里先用long double类型算一个高精度的浮点初值然后通过两个while循环把误差修正掉。就算初值差了一点最多也只需要几次整数加减乘就能回到正确位置。因为r最大不会超过1e9r*r的乘积用long long存得下不会溢出。如果你不喜欢浮点也可以用整数二分long long sqrt_floor(long long x) { long long lo 0, hi 1000000000LL; // 根据题目上限 long long ans 0; while (lo hi) { long long mid (lo hi) / 2; if (mid * mid x) { ans mid; lo mid 1; } else { hi mid - 1; } } return ans; }二分的每次判断是O(log l)n2e5时总共也就几百万次乘法完全跑得动。我个人建议在正式比赛里用浮点修正法代码短但如果还在学习阶段二分法更“讲道理”不容易被各种浮点玄学困扰。4.3 乘法溢出的另一个坑除了开方还有一个C基础问题也容易在这里暴露ll - yy必须用long long计算。如果你把l声明成int然后写l * l这个乘法是在int域内完成的l1e9时l*l1e18直接溢出int变成一个不可预测的负数后面一切都乱套。正确做法是读入时就存成long long。如果题目输入给的是int赋给long long变量后再做乘法也没问题但千万不要让两个int直接相乘。同理y*y也要确保是long long乘法最保险的写法是long long len l * l - 1LL * y * y;。这类溢出bug在C里特别隐蔽因为它不报错只是结果变成一个看起来没什么规律的负数continue掉整条鱼最后你只会觉得答案偏小根本想不到是乘法溢出。5. 完整C实现与逐段讲解下面是完整可AC的核心代码我按自己的习惯做了注释。这里用的就是“事件差分扫描浮点修正开方”的方案。#include bits/stdc.h using namespace std; using ll long long; struct Event { ll pos; int delta; bool operator(const Event other) const { return pos other.pos; } }; struct Fisherman { ll pos; int id; bool operator(const Fisherman other) const { return pos other.pos; } }; // 求 floor(sqrt(x))用浮点估算后做整数修正 ll sqrt_floor(ll x) { ll r sqrt((long double)x); while ((r 1) * (r 1) x) r; while (r * r x) --r; return r; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; ll l; cin n m l; vectorEvent events; events.reserve(2 * n); for (int i 0; i n; i) { ll x, y; cin x y; // 鱼离岸线太远直接不可能被钓到 if (y l) continue; ll len l * l - y * y; ll d sqrt_floor(len); // 区间 [x-d, xd]拆成起点 1、终点后一位 -1 events.push_back({x - d, 1}); events.push_back({x d 1, -1}); } vectorFisherman fishers(m); for (int i 0; i m; i) { cin fishers[i].pos; fishers[i].id i; // 记住原始顺序最后按顺序输出 } sort(events.begin(), events.end()); sort(fishers.begin(), fishers.end()); vectorint ans(m); int cur 0; int idx 0; for (const auto f : fishers) { // 把所有位置不超过当前渔夫坐标的事件都加进去 while (idx (int)events.size() events[idx].pos f.pos) { cur events[idx].delta; idx; } ans[f.id] cur; } for (int i 0; i m; i) { cout ans[i] \n; } return 0; }有几个点值得多说一句。第一事件数组里同一个坐标可能有多个1和-1它们混在一起也没关系。因为我们扫描渔夫时是按事件逐个执行的同一个pos下的多个事件在到达该pos时都会被依次累加进cur最终的效果和按差分前缀和计算完全一致。不需要对同一个pos的事件预先合并。第二右端点事件用的是x d 1而不是x d。因为区间是闭区间渔夫坐标恰好等于xd时应该算作覆盖。如果把-1放在xd那扫描到xd时会先加后减覆盖数白白少1。放在xd1xd及之前的位置都不会触发这个-1事件覆盖数才正确。第三渔夫坐标排序后是递增的事件指针idx只会从左往右走不会回退所以整个扫描是线性的。这也是事件差分比每次二分找区间要快的原因之一。我拿一组小数据验证过这个代码。假设l5一条鱼在(0, 3)区间算出来是[-4, 4]。五个渔夫坐标为-5、-4、4、5、0输出应该是0、1、1、0、1。运行结果完全一致。再比如鱼在(0, 5)l5d0区间是[0,0]只有渔夫恰好站在0处才能钓到。这个用例可以重点检查右端点的出队逻辑。6. 我实际刷这道题踩过的坑和验证过程最后这部分写点实战心得。我刷这题不是一遍过的中间经历了从TLE到WA再到AC的完整过程每个阶段都有值得记录的东西。6.1 第一次尝试暴力枚举TLE一开始没多想直接双重循环。测试小数据没问题一上大数据就卡死。当时我用的是在线评测的小数据点勉强能出结果但自己生成一个2e5规模的随机数据一测跑了十几秒还没结束瞬间意识到复杂度完全不行。这说明刷题有个好习惯很重要动手之前先算一下复杂度上限而不是先写再说。6.2 第二次尝试long long溢出的WA换成区间覆盖做法之后第一个版本把l声明成int。小数据没问题一到坐标接近1e9的测试点就WA。我调了很久才发现是l * l在int域溢出。这种错误在本地往往不会暴露因为小数据根本碰不到溢出边界。以后凡是坐标可能到1e9的题乘法一律用long long别心存侥幸。6.3 第三次尝试sqrt精度导致差1修正溢出后大部分数据能过了但用随机对拍时发现答案偶尔比暴力的结果少1。定位后确认就是第四节说的那个浮点问题。后来用修正法重写sqrt_floor再对拍就完全一致了。这件事给我的教训是涉及sqrt()转整数的题不管数据多小都必须做边界修正否则就是赌博。6.4 对拍是刷题最好的习惯我后面能快速确认代码正确靠的就是写了一个O(n*m)的暴力程序配合随机数据生成器和正经解对拍。对拍的具体流程很简单写一个暴力solve写一个快速solve生成随机的n、m、l和鱼、渔夫坐标两边输出对比不一致就停下来打印数据。这个小工具帮我一次性抓出了浮点和输出顺序两个隐藏问题。6.5 输出顺序的陷阱有段时间我把渔夫排序后直接按排好的顺序输出答案结果答案数组看起来“很对”但就是不匹配样例。后来才意识到题目要求按输入顺序输出每个渔夫的结果而我排序打乱了原始次序。解决办法就是给渔夫带id扫描结束后按id写回最后统一输出。这个细节在新手题解里经常被一笔带过但实际写代码时特别容易犯。再说一个小技巧测试极端数据时可以故意把鱼放在yl的位置这样d0区间就是一个点可以用来验证闭区间边界还可以把渔夫放在区间端点的正左一格、正右一格确保1和-1事件的触发时机没有偏差。这道题给我最大的感受是代码本身确实不难但每一个细节都有坑几何转化、整数开方、闭区间出队、long long溢出、输出顺序。能一次性全踩对的人不多所以它才值得被收进刷题打卡列表里反复做。如果你正在备战信奥建议把这道题当成“区间覆盖浮点精度”的双重训练题不要看一眼题解就跳过。自己推一遍再写一遍再对拍一遍这套流程走完收获比刷十道模板题都大。