Atcoder #beginner224 C题

Atcoder #beginner224 C题

题目描述：

坐标上N个点，求可以构成的三角形的数目

文章目录

• • • 代码一
    • 代码二

思路：
枚举N个顶点所可以构成的所有连线，对于每一条连线，遍历其余的所有点，判断该点与该线段是否共线。

代码一

通过斜率判断是否共线。

#include 
using namespace std;

const int N = 300; //点的数目
int x[N], y[N]; //分别存储x坐标和y坐标

bool f(int i, int j, int k) 
{
    if (x[i] == x[j] && x[i] == x[k]) return false;
    if (y[i] == y[j] && y[i] == y[k]) return false;
    if ((y[k] - y[j]) * (x[j] - x[i]) == (y[j] - y[i]) * (x[k] - x[j])) return false;
    return true;

}
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++)
        cin >> x[i] >> y[i];
        
    int cnt = 0;
    for (int i = 0; i < n; i ++)
        for (int j = i + 1; j < n; j ++) //枚举所有连线（无重复）
            for (int k = 0; k < n; k ++) //判断点k是否在这条连线上
            {
                if (k == i || k == j) continue; //若与之前点发生重复则跳过
                if (f(i, j, k)) cnt ++; //不共线，则cnt++
            }
    cout << cnt / 3; //每个三角形被计了3次
    return 0;
}

代码二

通过三点所围的面积是否为0来判断3点是否共线。

已知 A ( x 1 , y 1 ) , B ( x 2 , y 2 ) , C ( x 3 , y 3 ) A(x_1, y_1),B(x_2,y_2),C(x_3,y_3) A(x1​,y1​),B(x2​,y2​),C(x3​,y3​)，则 S △ A B C = x 1 y 2 − x 2 y 1 + x 2 y 3 − x 3 y 2 + x 3 y 1 − x 1 y 3 2 S_{△ABC} = frac{x_1y_2-x_2y_1+x_2y_3-x_3y_2+x_3y_1-x_1y_3}{2} S△ABC​=2x1​y2​−x2​y1​+x2​y3​−x3​y2​+x3​y1​−x1​y3​​

bool f(int i, int j, int k)
{
    if (x[i] * y[j] - x[j] * y[i] + x[j] * y[k] - x[k] * y[j] + x[k] * y[i] - x[i] * y[k] == 0) return false;
    return true;
}