[数据结构与算法]P6341の题解

题目传送门

$Description$

给出平面内的 n 个点，计算有多少不同的直角三角形，满足其顶点均为给出的点。两个直角三角形不同当且仅当它们存在至少一个顶点不同。

题目意思就是在给出的 n 个点中，任意选 3 个点，且这三个点组成的三角形恰为$Rt\Delta$ （直角三角形）。

输入的第一行为给出的点的数目 n，第 2 到 n+1 行分别为这 n 个点的坐标 x和y，分别是点的 x 坐标和 y 坐标。

思路

我们可以通过勾股定理来求出两个点的直线距离，也可以用勾股定理来判断是否是直角三角形。

直角三角形满足：

1. 三角形中有一角的角度为90°

2. 若 a2+b2=c2 的平方，则以a、b、c为边的三角形是以c为斜边的直角三角形（勾股定理的逆定理）。

3. 若一个三角形30°内角所对的边是某一边的一半，那么这个三角形是以这条长边为斜边的直角三角形。

4. 直角三角形中，斜边上的中线等于斜边的一半（即直角三角形的外心位于斜边的中点，外接圆半径R=C/2）。该性质称为直角三角形斜边中线定理。

而我们这题用到的是判断 2，即勾股定理逆定理。由于这题的数据好像没有题目所说那么大，所以这种 $O(n^3)$ 的复杂度应该是能够AC的。鄙人太蒻，暂时没有想出别的更好的方法。

$Answer$

Record

上代码：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
#define for(i,j,n) for(int i=j+1;i<=n;++i)
const int maxn=1510;

ull x[maxn],y[maxn],mp[maxn][maxn];

inline int read() {
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}

/*

inline double dist(int i,int j) {
	return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
} 求两点距离的平方 

*/

signed main() {
	
	std::ios::sync_with_stdio(false);
	int n=read(),ans=0;
	
	for(i,0,n) {
		x[i]=read();
		y[i]=read();
		for(j,0,i-1) {
			mp[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]); //因为计算勾股的时候要平方，所以这里不用求根，下同 ↓ 
			// 或是：mp[j][i]=dist(j,i);
		}
	}
	
	for(i,0,n)
		for(j,i,n)
			for(k,j,n)
				if(mp[i][j]+mp[i][k]==mp[j][k]||mp[i][j]+mp[j][k]==mp[i][k]||mp[i][k]+mp[j][k]==mp[i][j])
					ans++;
					
	printf("%d",ans);
	return 0;
}