每日一题 0126

（2022.01.26）每日一题 检测正方形

芜湖，中等题，第一想法，算出所有的点，遍历查找，属实脑子不对劲。然后想到使用哈希表，存储所有的点出现及其出现的次数。

因为已知了一个查询点，那么轴对齐正方形的各个顶点就会非常好算。当查询点\((x,y)\)存在轴对齐正方形时，必然在点集中存在与其 \(x\) 值或 \(y\) 值相同的点，即与查询点构成的直线平行于 \(x\) 轴或 \(y\) 轴。所以我们使用unorderd_map构建哈希表，记录点出现的次数。我们以 \(y\) 值相同，\(x\) 值不同来找第一个点，当我们找到该点时，我们可以计算出正方形的剩余两个点，我们只要去判断这两个点是否存在于哈希表中，并计算次数即可。

为了方便表示，我们设查询点\(X=(x,y)\),参照点\(Y=(x1,y)\)，那么剩下的两个点的坐标分别是\(((x,y+abs(x-x1)),(x1,y+abs(x-x1))\)或\((x,y-abs(x-x1)),(x1,y-abs(x-x1)))\)。最后计算对应两点的个数相乘后相加即可，当然还要乘以我们参照点的个数。最后需要注意的是一定要将与我们查询点相同的点筛出，我就是一开始忘记筛出了，就会出错，这样按照代码的逻辑也是可以计算的，就是计算与查询点相同的点的个数相乘，相加，再乘以参照点的个数。总而言之就是很弱智的错误，用于提醒一下自己。

class DetectSquares {
public:
    unordered_map> cnt;
    DetectSquares() {

    }
    
    void add(vector point) {
        int x = point[0], y = point[1];
        cnt[y][x]++;
    }
    
    int count(vector point) {
        int x = point[0];
        int y = point[1];
        int res = 0;
        if(!cnt.count(y)){
            return 0;
        }
        for(auto& tmp: cnt[y]){
            int tmp_x = tmp.first;
            if(tmp_x == x) continue;
            // int edge = (x - tmp_x)>0?(x-tmp_x):(tmp_x - x);
            // int edge = abs(x-tmp_x);
            int p1_x = x;
            int p1_y = y - edge;
            int p2_x = x;
            int p2_y = y + edge;
            int p3_x = tmp_x;
            int p3_y = y - edge;
            int p4_x = tmp_x;
            int p4_y = y + edge;
            res+= tmp.second*(cnt[p1_y][p1_x]*cnt[p3_y][p3_x] + cnt[p2_y][p2_x]*cnt[p4_y][p4_x]);
        }
        return res;
    }
};
/**
 * Your DetectSquares object will be instantiated and called as such:
 * DetectSquares* obj = new DetectSquares();
 * obj->add(point);
 * int param_2 = obj->count(point);
 */