Codeforces 1146H Satanic Panic

题解

首先，总的方案数为 $C_n^5$Cn5​，现在要减去不合法的
不合法的一共有下图的两种情况
一种是四边形中有一个点，另一种是三角形中有两个点
对于第一种情况，枚举所有三角形，设三角形内部有 $x$x个点，则有 $x\times \frac{n-4}{2}$x×2n−4​种不合法的情况，除2是因为第一种情况会被算2次
对于第二种情况， $x\times \frac{n-4}{4}$x×4n−4​才是不合法的情况的数量
同样， $\frac{x\ast (x-1)}{2}$2x∗(x−1)​也能表示不合法的情况的数量
综合两种情况，计算是统一减去 $x\times \frac{n-4}{2}$x×2n−4​，再加上 $\frac{x\ast (x-1)}{2}$2x∗(x−1)​就是答案

如何枚举所有三角形呢？
我们用 $bitset$bitset记录每条线段左侧的点，对于三角形 $(i,j,k)$(i,j,k)
$f\left[i\right]\left[k\right]\mathrm{\&}f\left[j\right]\left[k\right]\mathrm{\&}f\left[k\right]\left[i\right]$f[i][k]&f[j][k]&f[k][i]
就是三角形内部的点，用 $count\left(\right)$count()函数很方便统计个数。

代码

#include<bits/stdc++.h>
#define N 1000010
#define INF 0x3f3f3f3f
#define eps 1e-10
// #define pi 3.141592653589793
// #define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef pair<int,int> pp;

struct node
{
	LL x,y;
	node (LL x=0,LL y=0):x(x),y(y){}
	node operator - (const node z) const{
		return node(x-z.x,y-z.y);
	}
	LL operator * (const node z) const{
		return x*z.y-y*z.x;
	}
}a[310];

bitset<302> f[301][301];

int main()
{
	int n;
	sc(n);
	for (int i=0;i<n;i++) scanf("%I64d%I64d",&a[i].x,&a[i].y);

	for (int i=0;i<n;i++)
		for (int j=0;j<n;j++) if (i!=j)
			for (int k=0;k<n;k++) if (k!=i && k!=j)
				f[i][j][k]=((a[j]-a[i])*(a[k]-a[i])>0);

	LL bas=(LL) n*(n-1)*(n-2)*(n-3)*(n-4)/120;
	LL t=0,tt=0;
	for (int i=0;i<n;i++)
		for (int j=i+1;j<n;j++)
			for (int k=i+1;k<n;k++) if (j!=k && f[i][j][k]){
				int ins=(f[i][j]&f[j][k]&f[k][i]).count();
				t+=ins*(ins-1)/2;
				tt+=ins;
			}
	cout<<bas-tt*(n-4)/2+t;

	return 0;
}