CF13D. Triangles

【题目链接】https://codeforces.com/problemset/problem/13/D

【题解】

一道非常经典而古老的三角形计数。

考虑三角形的有向面积。

显然有：$S_{ riangle ABC}=S_{ riangle OAB}+S_{ riangle OBC}+S_{ riangle OCA}$。

因此对每对点先统计一遍，再枚举三个点即可 $O(1)$ 计算。

效率 $O(n^3)$。

【代码】

#include<bits/stdc++.h>
const int inf=1<<30;
int cnt[510][510],n,m;
struct Vector
{
    long long x,y;
    Vector(long long _x=0,long long _y=0){x=_x;y=_y;}
    inline friend Vector operator - ( const Vector &u,const Vector &v ) { return Vector(u.x-v.x,u.y-v.y); }
    inline friend long long operator ^ ( const Vector &u,const Vector &v ) { return u.x*v.y-u.y*v.x; }
}A[510],B[510];
signed main()
{
    scanf("%d%d",&n,&m);
    for ( int i=1,x,y;i<=n;i++ ) scanf("%d%d",&x,&y),A[i]=Vector(x,y);
    for ( int i=1,x,y;i<=m;i++ ) scanf("%d%d",&x,&y),B[i]=Vector(x,y);
    Vector p=Vector(-inf,-inf);
    for ( int i=1;i<=n;i++ ) for ( int j=1;j<=n;j++ ) if ( ((A[i]-p)^(A[j]-p))>0 )
    {
        for ( int k=1;k<=m;k++ ) cnt[i][j]+=(((A[i]-p)^(B[k]-p))>0)&(((A[j]-A[i])^(B[k]-A[i]))>0)&(((p-A[j])^(B[k]-A[j]))>0);
        cnt[j][i]=-cnt[i][j];
    }
    int ans=0;
    for ( int i=1;i<=n;i++ ) for ( int j=i+1;j<=n;j++ ) for ( int k=j+1;k<=n;k++ ) ans+=(cnt[i][j]+cnt[j][k]+cnt[k][i])==0;
    return !printf("%d",ans);
}