LuoguLOJ分析暴力就是把所有圆排序后直接 $\mathcal{O}(n^2)$ 模拟。考虑用 KD-Tree 优化模拟过程。我们把每个圆看作它的外接矩形，然后对于当前删去的圆在 KD-Tree 上递归，如果圆与矩形没有交则不会更新，可以直接返回。然后建树时按方差选维度就可以过了。代码// =================================== // author: ...
LuoguLOJ分析暴力就是维护一个大小为 $k$ 的小根堆，然后 $\mathcal{O}(n^2)$ 枚举。考虑用 KD-Tree 优化。对于每个点在 KD-Tree 上递归，如果当当前矩形的最大距离比堆顶小则不可能更新答案，可以直接返回。因为是每对点算了两遍所以堆的大小应为 $2k$，为了方便可以先插 $2k$ 个 $0$ 进去。代码// =======================...
Luogu分析还是 KD-Tree 板子。插入时利用替罪羊树重构那一套保证平衡。查询时判断查询矩形和当前矩形是否有交，如果完全包含直接返回当前矩形和，部分包含就递归下去，否则返回 $0$。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ===...
Luogu分析KD-Tree 板子。插入时可能会让 KDT 不平衡，用类似于替罪羊树的方式定期重构即可。查询时利用到矩形的最短距离剪枝。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =============================...