解题思路

这是一道平面几何问题，主要思路如下：

  1. 判断三点是否能构成三角形：

    • 三点不共线即可构成三角形
    • 使用斜率判断三点是否共线：
    • 为避免除法，转换为乘法形式：

  2. 使用三重循环遍历所有可能的三点组合：

    • 第一层循环： 从 到
    • 第二层循环： 从 到
    • 第三层循环： 从 到

代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> points(n);
    
    // 读入所有点的坐标
    for(int i = 0; i < n; i++) {
        cin >> points[i].first >> points[i].second;
    }
    
    int res = 0;
    // 三重循环遍历所有可能的三点组合
    for(int i = 0; i < n-2; i++) {
        auto x = points[i];
        for(int j = i+1; j < n-1; j++) {
            auto y = points[j];
            for(int k = j+1; k < n; k++) {
                auto z = points[k];
                // 判断三点是否共线
                if((z.second - x.second)*(y.first - x.first) != 
                   (y.second - x.second)*(z.first - x.first)) {
                    res++;
                }
            }
        }
    }
    
    cout << res << endl;
    return 0;
}

import java.util.*;

public class Main {
    static class Point {
        int x, y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Point[] points = new Point[n];
        
        // 读入所有点的坐标
        for(int i = 0; i < n; i++) {
            points[i] = new Point(sc.nextInt(), sc.nextInt());
        }
        
        int res = 0;
        // 三重循环遍历所有可能的三点组合
        for(int i = 0; i < n-2; i++) {
            Point x = points[i];
            for(int j = i+1; j < n-1; j++) {
                Point y = points[j];
                for(int k = j+1; k < n; k++) {
                    Point z = points[k];
                    // 判断三点是否共线
                    if((z.y - x.y)*(y.x - x.x) != 
                       (y.y - x.y)*(z.x - x.x)) {
                        res++;
                    }
                }
            }
        }
        
        System.out.println(res);
    }
}

n = int(input())
points = []

# 读入所有点的坐标
for _ in range(n):
    x, y = map(int, input().split())
    points.append((x, y))

res = 0
# 三重循环遍历所有可能的三点组合
for i in range(n-2):
    x = points[i]
    for j in range(i+1, n-1):
        y = points[j]
        for k in range(j+1, n):
            z = points[k]
            # 判断三点是否共线
            if (z[1] - x[1])*(y[0] - x[0]) != (y[1] - x[1])*(z[0] - x[0]):
                res += 1

print(res)

算法及复杂度

  • 算法：暴力枚举 + 几何判断
  • 时间复杂度： - 三重循环遍历所有可能的三点组合
  • 空间复杂度： - 存储 个点的坐标