Open forever97 opened 4 years ago
https://forever97.github.io/2019/08/18/2019NOWCODER10F/
Problem给定$n(n \le 10^5)$个点的坐标$(x,y)$ 选择三条距离相邻距离为r的竖线和三条相邻距离为r的横线，使得线上的点数量最多 Solution考虑枚举横线的选取，数据结构维护竖线的极值 我们把相邻为r的三条竖线的值的和保存在第一条竖线上，即可数据结构维护 考虑枚举的横线和竖线的重复点部分，我们将枚举的横线上的点删除，修改竖线，统计完加回 每个点只会被删除三次，因此总
https://forever97.github.io/2019/08/18/2019NOWCODER10F/
Problem给定$n(n \le 10^5)$个点的坐标$(x,y)$ 选择三条距离相邻距离为r的竖线和三条相邻距离为r的横线，使得线上的点数量最多 Solution考虑枚举横线的选取，数据结构维护竖线的极值 我们把相邻为r的三条竖线的值的和保存在第一条竖线上，即可数据结构维护 考虑枚举的横线和竖线的重复点部分，我们将枚举的横线上的点删除，修改竖线，统计完加回 每个点只会被删除三次，因此总