题解

$O(n^3)$ 的解法是个人都会，所以我来教大家一个 $O(n^2\log n)$ 的解法。

思考一下如果一个三角形是直角三角形，那它得满足什么？

1. 有直角。
2. 符合勾股定理（即存在两边的平方和等于第三边）。

性质 2 想不出来怎么优化，所以我考虑性质 1。

注意到在平面直角坐标系内，如果一个角是直角，它的两边的解析式分别为 $y=k_1x+b_1,y=k_2x+b_2(k_1,k_2\not= 0)$，则有 $k_1\times k_2=-1$。如果两边解析式分别为 $y=b_1$ 和 $x=b_2$，也可以构成直角。

我们可以先预处理出每个边的解析式的 $k$ 值，然后枚举每个顶点， 计算它们作为直角顶点的个数，这个个数就是这个图内直角三角形的个数。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
int a[100005], b[100005], ans;
pair <int, int> mp[1505][1505];
int ct[1505];
int n;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
        	if(i == j) continue;
            int den = a[i] - a[j], num = b[i] - b[j];//用分数表达解析式
            if(den == 0) num = 1;//与 x 轴平行，k 用 0/1 表示
            else if(num == 0) den = 1;//与 y 轴平行，k 用 1/0 表示
            else{
                if(den < 0) den = -den, num = -num;//保证分母为正
                int gcd = __gcd(abs(den), abs(num));
                den /= gcd, num /= gcd;//约分
            }
            mp[i][++ct[i]] = {num, den};
        }
    }
    for(int i = 1; i <= n; i++){
    	sort(mp[i] + 1, mp[i] + ct[i] + 1);//聚集相等元素，以便计算
	}
    for(int i = 1; i <= n; i++){
    	for(int j = 1; j <= ct[i]; j++){
    		int den, num;
    		if(mp[i][j].second == 0) num = 0, den = 1;
    		if(mp[i][j].first == 0) num = 1, den = 0;
			else{
				den = -mp[i][j].first, num = mp[i][j].second;//计算与这条线垂直的线段的解析式
				if(den < 0) den = -den, num = -num;
			}
			auto idx1 = lower_bound(mp[i] + 1, mp[i] + ct[i] + 1, make_pair(num, den));//寻找在同一个点且与之垂直的线段
    		auto idx2 = upper_bound(mp[i] + 1, mp[i] + ct[i] + 1, make_pair(num, den));
    		ans += idx2 - idx1;
		}
    }
    cout << ans / 2;//加了两边，要除 2
    
    return 0;
}

时间复杂度：$O(n^2\log n)$。