【差分数组】个人练习-Leetcode-2249. Count Lattice Points Inside a Circle

题目链接：https://leetcode.cn/problems/count-lattice-points-inside-a-circle/description/

题目大意：给出一系列圆的圆心坐标和半径，求在这些圆内部（边缘也算）的格点的数量。

思路：简单的思路就是暴力遍历。稍微优化一下，就是缩小一下范围，确定x, y坐标的上下限。通过是能通过，但复杂度还是$O(N^3)$左右。

看题解学到了差分数组法：
对每一个纵坐标$y$，画一条横线，对于一个圆如过经过内部点，必然从左到右穿过两个横坐标$x_1,x_2$（在圆上的情况就是$x_1=x_2$）。

那么就对这个$y$坐标的差分数组，经过左端点时+1，经过右端点时-1。那么之后只需要遍历$x$坐标，保留一个和cur，当cur > 0时就在圆内。我们可以让$x_2$都往右偏移一位，这样对于在圆上的情况也能保证计算在内。

完整代码

class Solution {
public:int countLatticePoints(vector<vector<int>>& circles) {int maxx = 0, maxy = 0;for (auto ck : circles) {maxx = max(maxx, ck[0] + ck[2]);maxy = max(maxy, ck[1] + ck[2]);}vector<vector<int>> d(maxy+1, vector<int>(maxx+2, 0));for (auto ck : circles) {int x = ck[0], y = ck[1], r = ck[2];for (int j = y+r, i1 = x, i2 = x; j >= y; j--) {while ((i1-x)*(i1-x) + (j-y)*(j-y) <= r*r)i1--;while ((i2-x)*(i2-x) + (j-y)*(j-y) <= r*r)i2++;i1++;d[j][i1]++;d[j][i2]--;}for (int j = y-r, i1 = x, i2 = x; j < y; j++) {while ((i1-x)*(i1-x) + (j-y)*(j-y) <= r*r)i1--;while ((i2-x)*(i2-x) + (j-y)*(j-y) <= r*r)i2++;i1++;d[j][i1]++;d[j][i2]--;}}int res = 0;for (int j = 0; j <= maxy; j++) {for (int i = 0, cur = 0; i <= maxx; i++){cur += d[j][i];if (cur > 0)res++;}}return res;}
};