P7553
b1ngxu
·
·
题解
通过观察可以发现：
一条线段 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。
$aot$ 的计算同样枚举一个点 $A$，对剩下的点进行极角排序，枚举到一个点 $B$ ，找到所有的 $(C,D)$ 使得 $\angle BAC\leqslant\pi$ 且 $\angle CAD\leqslant\pi$ 且 $\angle BAD\leqslant\pi$ 的合法对数即可。
具体细节可以看代码
```c
#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();
}
```