[CF1025F]Disjoint Triangles[极角排序+组合计数]

题意

平面上有 \(n\) 个点，选出六个点构成两个三角形，问有多少种构造方式使得两个三角形没有交集。

\(n\leq 2000\)

分析

• 枚举连接两个三角形的两个顶点，同时能够将两个三角形划分在直线两侧的直线。

• 考虑每个点和 \(n-1\) 个点连边，这些边按照极角排序，并维护直线左侧有多少个点(如果跨过极角等于 \(\pi\) 就再加一倍直线，同时弧度 \(+2\pi\))，那么答案增加量就是 \(\binom{{cnt}_l}{2}\times\binom{n-2-{cnt}_l}{2}\)。

• 每对三角形会有两条直线计算到，所以最后答案除以2.

• 时间复杂度 \(O(n^2logn)\) 。

代码

#include<bits/stdc++.h>

using namespace std;

#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].lst,v=e[i].to)

#define rep(i,a,b) for(int i=a;i<=b;++i)

#define pb push_back

typedef long long LL;

inline int gi(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch))	{if(ch=='-') f=-1;ch=getchar();}

	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}

	return x*f;

}

template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}

template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}

typedef double db;

const db INF=1.0*1e14,pi=acos(-1.0);

const int N=4004;

int n;

LL ans;

db ang[N],x[N],y[N];

LL C(int n){

	return 1ll*n*(n-1)/2;

}

int main(){

	n=gi();

	rep(i,1,n) scanf("%lf%lf",&x[i],&y[i]);

	rep(o,1,n){

		int ndc=0;

		rep(i,1,n) if(o^i) ang[++ndc]=atan2(y[i]-y[o],x[i]-x[o]);

		sort(ang+1,ang+ndc+1);

		rep(i,1,n-1) ang[++ndc]=ang[i]+2*pi;

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

			while(ang[j]-ang[i]<=pi) ++j;

			int l=j-i-1,r=n-2-l;

			ans+=C(l)*C(r);

		}

	}

	printf("%lld\n",ans>>1);

	return 0;

}