JZOJ – 3493 三角形

Time Limit : 1000ms
Memory Limit : 256MB

Description

平面上有 $n$ 个点，求出用这些点可以构成的三角形数。

Input

第一行一个整数 $n$ 。
接下来 $n$ 行，每行两个整数，表示点的坐标。

Output

输出仅一个整数，表示所求答案。

Sample Input

Sample Output

Data Constraint

对于 50% 的数据，n <= 300。
对于 100% 的数据，n <= 3000 ，坐标的绝对值不超过 10^4 ，保证没有重合的点。

解题思路

暴力解法：枚举三个点，判断这三个点是否在同一条直线上，如果再同一条直线上则不能构成三角形。

思考如何判断三个点是否在同一直线上。

我们可以通过计算斜率的方式判断三个点是否在同一条直线上。

这个做法是 $O(n^3)$ 的，可以得到50分。

思考从斜率上下手优化，考虑容斥。

如果每个点都能被选择，共计有 $ n \times (n-1) \times (n-2) $种情况。

枚举一个点 $i$，对所有其他点计算斜率（这里需要特判 $x[i] == x[j] $ 的情况，点的数量记为 cnt）

$ans$ 减去 $ \frac{cnt \times (cnt-1)}{2} $

再将斜率排序，记录对于每一个点 $j$ 斜率相同的点有 $k$ 个，这说明有 $k-1$ 个点可以与点 $j$ 和点 $i$ 构成一条直线， $ans$ 减去 $k-1$ 即可

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 3000 + 10;

inline int read(){
    int x = 0;
    int p = 1;
    char ch = getchar();

    while(ch < '0' || ch > '9'){
        if(ch == '-')
            p = 0;
        ch = getchar();
    }

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return p ? x : (-x);
}

int n;
int x[MAXN], y[MAXN];
long long ans;

int main(){

    freopen("triangle.in", "r", stdin);
    freopen("triangle.out", "w", stdout);

    n = read();

    for(register int i=1; i<=n; i++){
        x[i] = read();
        y[i] = read();
    }

    ans = ((long long)(n * (n-1))/2 * (n-2))/3;

    for(register int i=1; i<=n; i++){

        double tmp[MAXN]={};
        int tmp2 = 0;
        int cnt = 0;

        for(register int j=i+1; j<=n; j++){
            if(x[i] == x[j])
                tmp2++;
            else
                tmp[cnt++] = (double)(y[j] - y[i]) / (double)(x[j] - x[i]);
        }

        ans -= tmp2 * (tmp2-1) /2;
        tmp2 = 1;

        sort(tmp, tmp+cnt);

        for(register int j=1; j<cnt; j++){
            if(tmp[j] == tmp[j-1])
                tmp2++;
            else
                tmp2 = 1;

            ans -= tmp2 - 1;
        }
    }

    printf("%lld", ans);
    return 0;
}

[题解] JZOJ – 3493 三角形

BLOG