题解(有写注释)

O(n3)O(n2logn)都不够不如O(n2)

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<utility>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> Point;

// 计算最大公约数
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 归一化向量
pair<ll, ll> normalize(ll dx, ll dy) {
    if (dx == 0 && dy == 0) return {0, 0};
    
    ll g = gcd(abs(dx), abs(dy));
    dx /= g;
    dy /= g;
    
    // 确保方向一致性（第一象限或正y轴）
    if (dx < 0 || (dx == 0 && dy < 0)) {
        dx = -dx;
        dy = -dy;
    }
    
    return {dx, dy};
}

int main() {
    int n;
    cin >> n;
    vector<Point> points(n);
    
    for (int i = 0; i < n; i++) {
        cin >> points[i].first >> points[i].second;
    }
    
    ll ans = 0;
    
    // 枚举每个点作为直角顶点
    for (int i = 0; i < n; i++) {
        Point O = points[i];
        
        // 统计从O点出发的各个方向向量的数量（归一化后）
        map<pair<ll, ll>, int> dirCount;
        
        for (int j = 0; j < n; j++) {
            if (j == i) continue;
            
            ll dx = points[j].first - O.first;
            ll dy = points[j].second - O.second;
            
            auto norm_dir = normalize(dx, dy);
            dirCount[norm_dir]++;
        }
        
        // 对于每个方向，找与之垂直的方向
        for (auto &dir : dirCount) {
            ll dx = dir.first.first;
            ll dy = dir.first.second;
            
            if (dx == 0 && dy == 0) continue;
            
            // 垂直方向有两种表示方法，我们选择一种标准形式
            pair<ll, ll> perpendicular;
            
            if (dx == 0) {
                // 垂直方向是水平方向
                perpendicular = {1, 0};
            } else if (dy == 0) {
                // 垂直方向是垂直方向
                perpendicular = {0, 1};
            } else {
                // 一般情况：(dx, dy) 的垂直方向是 (-dy, dx) 或 (dy, -dx)
                // 我们选择归一化后的形式
                perpendicular = normalize(-dy, dx);
            }
            
            if (dirCount.find(perpendicular) != dirCount.end()) {
                ans += dir.second * dirCount[perpendicular];
            }
        }
    }
    
    // 每个直角三角形被计数2次（两个直角边方向）
    cout << ans / 2 << endl;
    return 0;
}