# 2013. Detect Squares

## naive

At most 3000 calls in total will be made to add and count

把所有點都去試試看 其他三個點是否存在,  超級窮舉,  3000\*3000 => 爆炸

## using x, y range, 對角線的想法

* `0 <= x, y <= 1000`

1. `首先紀錄所有點`
2. `count() 時, 把 input（point[0], point[1]）當作 x, y 起點`

```
(i, j) 對角線的點, 其他兩點會是...

for i to 1000
x = point[0], y =point[1]
d = abs(i - x)

so 上對角線的點: (i, j)
j = y+d               

i,j     [ x, j]

[i, y]    x,y


下對角線的點: (i, j)
j = y-d               

[i, y]    x,y

i, j      [x, j]
```

`在 x 軸上窮舉 i = 0~1000 :  那距離 d = abs(i-x)`

利用這個距離

`去算對角線（i, j）（上對角線, 下對角線）, 然後去找是不是有符合的其他兩個點`

數量就是這三個點的數量乘積

```
T: count: O(1000) , add: O(1)
S: O(1000*1000)
```

```java
class DetectSquares {

    int[][] pCounts;
    public DetectSquares() {
        pCounts = new int[1001][1001];
    }
    
    public void add(int[] point) {
        pCounts[point[0]][point[1]]++;
    }
    
    public int count(int[] point) {
        int x = point[0];
        int y = point[1];
        int res = 0;
        for (int i = 0; i <= 1000; i++) {
            int dist = Math.abs(i - x);
            if (dist == 0) { // if 點重合 pass
                continue;
            }
            
            int j = y + dist;
            if (j >= 0 && j <= 1000) {
                res += pCounts[i][j]*pCounts[x][j]*pCounts[i][y];
            }
            
            j = y - dist;
            if (j >= 0 && j <= 1000) {
                res += pCounts[i][j]*pCounts[x][j]*pCounts[i][y];
            }
        } 
        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);
 

for i to 1000
x = point[0], y =point[1]
d = abs(i - x)

so 
j = y+d               

i,j     [ x, j]

[i, y]    x,y


j = y-d               

[i, y]    x,y

i, j      [x, j]

T: count: O(1000) , add: O(1)
S: O(1000*1000)
 */
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/math/square/2013.-detect-squares.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.