7883

- 设 $f(l,r)$ 为分解与合并区间 $[l,r]$ 的函数。 - 设 $g(l,r)$ 为区间 $[l,r]$ 中的最近点对距离。 - 设 $dis(a_i,a_j)=\sqrt{(a_i.x-a_j.x)^2+(a_i.y-a_j.y)^2}$。 二分算法显然易见。 首先，将 $p_i$ ......

这是一篇**决策单调性**题解，好像现在还没有相同做法的题解。 还是类似的分治方式，每次点分成左右两半求两边贡献，再处理跨区间贡献。 但是有一种新的处理贡献方式：决策单调性。 先将两边点各自按照纵坐标升序排序，然后对每个左半边的点找最近的点。怎么找呢？考虑设置两个指针，分别指向纵坐标升序的左边第 $ ......

题目地址 题意：给出n个点，求最近的两个点距离的平方 Solution 分治法 dfs(i,j)表示在i，j上的最近点距离的平方，问题在于如何将两个区间的合并 原题解（囧仙） 对于区间长度等于2的区间，直接返回距离，等于1则返回无限 以mid为中心，|x[mid]-x[i]|<res的点都统计一遍， ......