Problem E Hidden squares

The typical Hidden words game can be modified to generate other problems. In particular, geometric figures can be found in them.

Given n rows and columns of capital letters, and a capital letter, we want to count the number of squares in the grid  with vertices in positions in the grid where that letter appears.

The Input

The input will consist of a series of problems, with each problem in a series of lines. In the first line the dimension of the grid (n) is indicated, in the second line appears the number of letters (m) for which we want to calculate the number of squares, and in consecutive lines the n rows of letters, each row in a line, and without separation between letters in the same row. When the input of a problem finishes the next problem begins in the next line. The input finishes when 0 appears as the dimension of the grid. The number of rows of each grid is less than or equal to 100.

The Output

The solutions of the different problems are separated by a black line. For each problem in the input and each letter in the input of the problem a line is written with the letter and the number of squares for this letter, separated by a space. For example, in the grid

 

AAA

AAA

BAB

the squares with vertices in A are:

 

AA-

AA-

---

 

-AA

-AA

---

 

-A-

A-A

-A-

Sample Input

3

2 

AAA

AAA

BAB

A

B

4

2

ABBA

BBBB

ABBB

ABBA 

A

B

0

Sample Output

A 3

B 0

 

A 1

B 8

---

題目描述：

找到平面整數點座標所形成的正方形個數，包含斜的正方形。

題目解法：

窮舉兩點，拉向量查找另外兩點。

#include <stdio.h>
#include <set>
#include <algorithm>
using namespace std;
struct Pt {
    int x, y;
    Pt(int a=0, int b=0):
        x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(x != a.x)
            return x < a.x;
        return y < a.y;
    }
};
int cntSquare(Pt D[], int n) {
    sort(D, D+n);
    set<int> S[105];
    int i, j, k;
    for(i = 0; i < n; i++)
        S[D[i].x].insert(D[i].y);
    int x, y, ret = 0;
    for(i = 0; i < n; i++) {
        for(j = i+1; j < n; j++) {
            int dx = D[j].x - D[i].x;
            int dy = D[j].y - D[i].y;
            x = D[i].x - dy;
            y = D[i].y + dx;
            if(-dy < 0)    continue;
            if(x < 0 || x >= 105)
                continue;
            if(S[x].find(y) == S[x].end())
                continue;
            x = D[j].x - dy;
            y = D[j].y + dx;
            if(x < 0 || x >= 105)
                continue;
            if(S[x].find(y) == S[x].end())
                continue;
            ret++;
        }
    }
    return ret;
}
int main() {
    int cases = 0;
    int n, m;
    int i, j, k;
    Pt D[10005];
    char g[105][105], s[105];
    while(scanf("%d %d", &n, &m) == 2 && n) {
        for(i = 0; i < n; i++)
            scanf("%s", &g[i]);
        if(cases++)    puts("");
        while(m--) {
            scanf("%s", s);
            int pn = 0;
            for(i = 0; i < n; i++)
                for(j = 0; j < n; j++)
                    if(g[i][j] == s[0])
                        D[pn++] = Pt(i, j);
            printf("%s %d\n", s, cntSquare(D, pn));
        }
    }
    return 0;
}
/*
3
2
AAA
AAA
BAB
A
B
4
2
ABBA
BBBB
ABBB
ABBA
A
B
*/