自动搬运

查看原文

来自洛谷，原作者为

	b1ngxu 2054.

搬运于2025-08-24 22:30:57，当前版本为作者最后更新于2021-05-04 19:44:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

通过观察可以发现： 一条线段 $AB$ 被另一条线段 $CD$ 穿过等价于四边形 $ADBC$ 是凸的。

考虑通过计数来代替判定，定义 $all[A][B]$ 表示以 $AB$ 为对角线的四边形个数，$aot[A][B]$ 表示以 $AB$ 为对角线且 $\angle A\geqslant\pi$ 的凹四边形个数。

当 $aot[A][B]+aot[B][A]=all[A][B]=all[B][A]$ 时表示 $AB$ 是满足条件的边，实际意义为以 $AB$ 为对角线的四边形全为凹四边形。

目前为止问题已经转化成如何求 $aot$ 和 $all$。

$all$ 的计算枚举一个点 $A$，对剩下的点进行极角排序，枚举到一个点 $B$ ，找到所有的 $C$ 使得 $\angle BAC\leqslant\pi$ 的个数为 $k$，那么 $all[A][B]$ 就是 $k*(n-1-k)$。

$aot$ 的计算同样枚举一个点 $A$，对剩下的点进行极角排序，枚举到一个点 $B$ ，找到所有的 $(C,D)$ 使得 $\angle BAC\leqslant\pi$ 且 $\angle CAD\leqslant\pi$ 且 $\angle BAD\leqslant\pi$ 的合法对数即可。

具体细节可以看代码

#include<bits/stdc++.h>
#define title "title"
#define ll long long
#define ull unsigned ll
#define fix(x) fixed<<setprecision(x)
#define pii pair<int,int>
#define vint vector<int>
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i--)
#define Help freopen("a","r",stdin)
#define db double
#define ld long db
#define vii vector<pii>
#define fi first
#define se second
#define mp make_pair
using namespace std;
void Freopen()
{
	freopen(title".in","r",stdin);
	freopen(title".out","w",stdout);
}
int read()
{
	int g=0,f=1;
	char ch=getchar();
	while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){g=g*10+ch-'0';ch=getchar();}
	return g*f;
}
const int N=1005;
const db pi=acos(-1);
pair<db,int>st[N<<1];
pii p[N];
int n,su[N<<1],all[N][N],aot[N][N];
signed main()
{
	n=read();
	rep(i,1,n)
	{
		int x=read(),y=read();
		p[i]=pii(x,y);
	}
	rep(i,1,n)
	{
		int cnt=0;
		rep(j,1,n)if(i!=j)st[++cnt]=mp(atan2(p[j].se-p[i].se,p[j].fi-p[i].fi),j);
		sort(st+1,st+cnt+1);
		rep(j,1,cnt)st[j+cnt]=st[j],st[j+cnt].fi+=pi*2;
		int k=1;
		rep(j,1,cnt)
		{
			while(st[k+1].fi-st[j].fi<=pi)k++;
			su[j+cnt]=su[j]=k-j;
			all[i][st[j].se]=su[j]*(cnt-1-su[j]);
		}
		rep(j,1,cnt<<1)su[j]+=su[j-1];
		k=1;
		rep(j,1,cnt)
		{
			while(st[k+1].fi-st[j].fi<=pi)k++;
			aot[i][st[j].se]=su[k]-su[j]-(k-j)*(k-j-1)/2;
		}
	}
	
	int Ans=0;
	rep(i,1,n)rep(j,i+1,n)if(aot[i][j]+aot[j][i]==all[i][j])Ans++;
	cout<<Ans;
	return signed();
}