自动搬运

查看原文

来自洛谷，原作者为

	new_sea_cheng 忍者心得第25条：忍者不可以在别人面前流眼泪

搬运于2025-08-24 22:19:36，当前版本为作者最后更新于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;
}