leetcode/Problems/2013.cpp at master · DimitrijeDobrota/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class DetectSquares {
    using point_t = tuple<int, int>;

    unordered_map<int, unordered_set<int>> ys;
    static int cnt[1001][1001];

  public:
    DetectSquares() { memset(cnt, 0x00, sizeof(cnt)); }

    void add(const vector<int> &point) {
        const int x = point[0];
        const int y = point[1];

        cnt[x][y]++;
        ys[x].insert(y);
    }

    int count(const vector<int> &point) {
        const int x = point[0];
        const int y = point[1];
        int res = 0;

        for (const auto yp : ys[point[0]]) {
            const int len = abs(y - yp);
            if (!len) continue;
            if (x + len <= 1000) res += cnt[x][yp] * cnt[x + len][y] * cnt[x + len][yp];
            if (x >= len) res += cnt[x][yp] * cnt[x - len][y] * cnt[x - len][yp];
        }

        return res;
    }
};

int DetectSquares::cnt[1001][1001];