题解：P12506 「ROI 2025 Day2」沼泽里的青蛙
wNightOvO
·
·
题解
P12506 「ROI 2025 Day2」沼泽里的青蛙
A2ure_Sky：这个题解讲得很好。
一个二维平面内有 n 个点 (x_i,y_i)，每个点可以向与之欧几里得距离不超过 r 的点连无向边，求最后哪些点所在的连通块包含奇环。保证 2\le n\le 10^5,1\le r\le 10^9,0\le x_i,y_i\le 5\times 10^8。
一个一个连边显然有点慢，考虑快速合并信息，如果存在三个点两两互相可达，则这三个点的连通块存在三元环（奇环），并且如果两个连通块均已存在奇环且有边连接这两个连通块，则这两个连通块的边可以删除（因为已经存在奇环了，连不连边不影响答案）。
考虑在平面内分成若干个正方形，使得每个正方形内的点均可相互到达，比较好的选法是取边长为 \frac{\sqrt{2}}{2}r，当然为了方便这里取边长 b = \lceil\frac{r}{2}\rceil，如果一个正方形中存在三个及以上的点，那么这个正方形中已经存在三元环（奇环），否则这个正方形至多有两个点。考虑正方形与正方形之间的连边，首先由上文的性质可以知道已经存在奇环的正方形与已经存在奇环的正方形不用相互连边，那么能连边的就是没有奇环的正方形连存在奇环的正方形或另一个没有奇环的正方形，而又因为我们取的 b = \lceil\frac{r}{2}\rceil，所以只有以一个正方形为中心，向周围 5\times 5 的正方形才能连上边，不然一定超过 r 的范围，故每个正方形最多向周围 25 个正方形连边，并且有奇环的正方形（点数 \ge 3）连的全都是点数 \le 2 的正方形，也就是说每个点至多连接 50 条边，故边数为 O(n) 带一个 50 倍常数，最后跑一个黑白染色判断二分图即可。
时空复杂度 O(n)，带 50 倍常数。