P6316

new_sea_cheng · 2023-10-11 17:58:12 · 题解

传送门

思路

构建一个平面直角坐标系拿样例一来举例子，如图:

我们把输入的字符矩阵的左下角坐标设为（1，1），把每个字母点的坐标存入到一个数组，我们可以通过举几个例子来找规律，得到每个顶点的横坐标（n-i+1）和纵坐标（j），然后枚举每一个字母点，判断是否在一条直线上。

注意：在判断是否在一条直线的过程中，只需要判断斜率。

因为这里是三个点是否共线，就是先确定前两个点的直线是否与后两个点的直线重合，因为有一个点是公共点，所以不需要判断截距。

只用判断两条直线的斜率，斜率公式为：

判断公式为：

十字相乘为：

代码

#include <bits/stdc++.h>
#define int long long //这道题不开longlong也能过
using namespace std;
int n;
char ch;
int s = 0;
struct aaa {
    int x, y;//x是横坐标，y是纵坐标
} a[10010];
bool ff(int i, int j, int z) {//判断三个点是否在一条线段上
    int x1 = a[i].x, y1 = a[i].y;
    int x2 = a[j].x, y2 = a[j].y;
    int x3 = a[z].x, y3 = a[z].y;
    return (y1 - y2) * (x2 - x3) == (y2 - y3) * (x1 - x2);
}
signed main() {
    cin >> n;
    int now = 0;//存储点坐标的下标
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> ch;
            if (ch != '.') { //是字母
                now++;//先加是因为我的now初始值是0
                a[now].x = n - i + 1;//因为我们把输入的矩阵的左下角的点坐标设为（1，1），所以n-i+1为它的横坐标
                a[now].y = j;//纵坐标是j-1+1,也就是j
            }
        }
    }
    for (int i = 1; i <= now; i++) {//枚举每个字母点
        for (int j = i + 1; j <= now; j++) {
            if (j == i) continue;//三个点不能重复
            for (int z = j + 1; z <= now; z++) {
                if (z == j) continue;//同上
                if (ff(i, j, z)) s++;
            }
        }
    }
    cout << s;
    return 0;
}