【Codeforces 1025F】Disjoint Triangles | Mrsrz's blog

计算几何。

题目大意：

给定 $n$ 个点，求能找到几对三角形，满足它们的顶点是 $n$ 个点中的若干个，且不相交。

题解：

两个三角形没有相交，则必然存在两条内公切线，并且两个三角形分别在公切线两端。

我们枚举这条公切线上的两个顶点，令它们分别为两个三角形的顶点。然后求出两边分别有多少个点，再计数即可。

具体计算时，先枚举一个点，然后以这个点为原点对其他点极角排序，然后按照极角序枚举每一条公切线即可。可以通过二分或者双指针的方式得到两边分别有多少个点。

时间复杂度 $O(n^2\log n)$。

Code：

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
const double pi=acos(-1);
using namespace std;
const int N=2005;
struct point{
    int x,y;
    double T;
    inline bool operator<(const point&rhs)const{return T<rhs.T;}
}p[N],a[N];
int n;
long long ans=0;
inline long long calc(int x){return(x-1LL)*x/2;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d%d",&p[i].x,&p[i].y);
    for(int i=1;i<=n;++i){
        memcpy(a,p,sizeof a);
        swap(a[i],a[1]);
        for(int i=2;i<=n;++i)a[i].T=atan2(a[i].y-a[1].y,a[i].x-a[1].x);
        sort(a+2,a+n+1);
        for(int i=2;i<=n;++i)if(a[i].T-1e-13>0){
            int l=i,r=lower_bound(a+2,a+n+1,(point){0,0,a[i].T-pi})-a;
            int L=l-r;
            ans+=1LL*calc(L)*calc(n-2-L);
        }
    }
    printf("%lld\n",ans);
    return 0;
}