給定大小 的格子點，這些格子點中， 四點決定一個正方形（注意：斜的也算）。
現在，拿掉某一個點 (x,y) ，使得能構成正方形的格子點集合為：
問用這些格子點，能畫出多少種不同正方形（頂點不同即視為不同）。
第一行是測資數量 T ，
後面有 T 行，
每一行有 N x y ，
代表 的格子點， 刪掉點 。
對於每一筆測資，輸出對應的正方形數量。
測資數量不大於 100 筆
答案可能爆 int
Input:
6
3 1 1
3 1 2
3 2 2
4 1 1
4 1 2
4 2 2
Output:
4
3
2
17
15
13
想像一個由 格子點組成的框框，這個框框唯一決定了， 在框框邊線上可以構成的所有正方形組合，再移動這個框框，窮舉在 格子點中，不同的 的擺放位置。再以此方式，枚舉每一種 大小，就可以在不刪除某個點的情況下，求出 格子點可以畫出的不同正方形了。
在不刪除點的條件下，格子點可以畫出的正方形數量：
代表題目格子點大小， 代表框框大小。 掃過所有可能的 即可。
那麼，如何去掉以 為頂點的所有正方形呢？
一樣用上面框框的概念，用一個大小 的框框，讓框框的邊線貼著 ，繞一圈、數數量，即可求出所有以 為頂點的所有正方形數量了。
答案就是：
不刪掉 情況的所有正方形數量，減去所有以 為頂點的正方形數量
這個做法複雜度是 。
求出不刪掉點的正方形數量要 ，
求出以 為頂點的所有正方形數量要 。
聽說還有更快的做法。
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
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
long long T, n, x, y;
int main(void) {
ios::sync_with_stdio(false);
cin >> T;
while(T--) {
cin >> n >> x >> y;
long long tot = 0;
for (int i=2; i<=n; ++i) {
tot += (long long)(n-i+1)*(n-i+1)*(i-1);
}
long long w=0, h=0;
w = max(x-1,n-x);
h = max(y-1,n-y);
long long s = max(w,h);
#define IN() (tx>=1L&&ty>=1L&&tx+i<=n&&ty+i<=n)
for (int i=1; i<=s; ++i) {
int tx=x-i;
int ty=y-i;
if (IN()) --tot;
for (int j=0; j<i; j++) {
++tx; if(IN()) --tot;
}
for (int j=0; j<i; ++j) {
++ty; if(IN()) --tot;
}
for (int j=0; j<i; ++j) {
--tx; if(IN()) --tot;
}
for (int j=1; j<i; ++j) {
--ty; if(IN()) --tot;
}
}
cout << tot << '\n';
}
return 0;
}