明明码力已经严重不足了, 但还是有一些题口胡完看过解法就不想写了……
记一下吧, 看着也方便.
Codeforces 293 D
Link
我们发现两点连对角线造出的正方形面积是$\frac{(x_1- x_2)^2 + (y_1-y_2)^2}{2}$, 所以$x$和$y$就可以分开算了, 最后加起来除以总的点对数即可.
我们$O(坐标)$地确定每个$x$轴/$y$轴上的合法整点个数, 那么就可以前缀和优化快速求了, 维护几个和/次方乘积和之类的就可以了.
CQOI 老C的任务
KD树板题, 写不过就弃了, 矩形内部点求和.
