自动搬运

查看原文

来自洛谷，原作者为

	b6e0_ ‪

搬运于2025-08-24 21:21:51，当前版本为作者最后更新于2021-03-28 16:56:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题

题面的一个坑点是线段除端点外无交点而不是直线。

看到这 $10$ 的数据范围，明显复杂度带有 $n!$。可以全排列做，但是为了方便剪枝，采用搜索。

枚举到一个排列 $p$，将 $p_i$ 与 $p_{i+1}$（$p_n$ 与 $p_1$）之间连线，主要任务就是判断任意两条线段之间是否有交点。

对于线段 $AB$ 与 $CD$，它们之间有交点的充要条件是点 $C$ 和 $D$ 在直线 $AB$ 的两侧且点 $A$ 和 $B$ 在直线 $CD$ 的两侧。

考虑向量叉乘。若 $\vec a\times\vec b>0$，那么 $\vec b$ 在 $\vec a$ 的逆时针方向；若叉积小于 $0$，那么 $\vec b$ 在 $\vec a$ 的顺时针方向。于是，判断点 $C$ 和 $D$ 是否在直线 $AB$ 的两侧，就是判断 $\overrightarrow{AB}\times\overrightarrow{AC}$ 和 $\overrightarrow{AB}\times\overrightarrow{AD}$ 是否同号。如果同号，那么在同侧；如果异号，那么在两侧。题目保证了任意三点不共线，所以叉积为 $0$ 的情况不可能出现。判断点 $A$ 和 $B$ 在直线 $CD$ 的两侧同理。时间复杂度 $\mathcal O(n!n^2)$，这个其实跑不满。代码：

#include<bits/stdc++.h>
using namespace std;
struct point
{
	double X,Y;
}a[15];
int p[15],n,ans;//p为选择的下标
bool cho[15];//cho表示是否已经选择
inline double cross(point x,point y)//叉积，这里向量也用point表示了，懒得开一个新的struct
{
	return x.X*y.Y-x.Y*y.X;
}
inline bool intersection(point x1,point y1,point x2,point y2)//判断是否有交点，有交点返回true
{
	double abc=cross((point){y1.X-x1.X,y1.Y-x1.Y},(point){x2.X-x1.X,x2.Y-x1.Y});
	double abd=cross((point){y1.X-x1.X,y1.Y-x1.Y},(point){y2.X-x1.X,y2.Y-x1.Y});
	if((abc>0&&abd>0)||(abc<0&&abd<0))
		return false;
	swap(x1,x2);
	swap(y1,y2);
	abc=cross((point){y1.X-x1.X,y1.Y-x1.Y},(point){x2.X-x1.X,x2.Y-x1.Y});
	abd=cross((point){y1.X-x1.X,y1.Y-x1.Y},(point){y2.X-x1.X,y2.Y-x1.Y});
	return ((abc>0&&abd<0)||(abc<0&&abd>0));
}
void dfs(int d)
{
	if(d>n)
	{
		int i;
		for(i=2;i<n-1;i++)
			if(intersection(a[p[n]],a[p[1]],a[p[i]],a[p[i+1]]))
				break;//第一个与最后一个连成的线段与其他是否有交点也要判断
		if(i==n-1)
			ans++;
		return;
	}
	for(int i=1;i<=n;i++)
		if(!cho[i])
		{
			int j;
			p[d]=i;
			for(j=1;j<d-2;j++)
				if(intersection(a[p[d-1]],a[p[d]],a[p[j]],a[p[j+1]]))
					break;
			if(j>=d-2)
			{
				cho[i]=true;
				dfs(d+1);
				cho[i]=false;
			}
		}
}
int main()
{
	do
	{
		n++;
		cin>>a[n].X>>a[n].Y;
	}while(a[n].X!=0||a[n].Y!=0);
	dfs(1);
	cout<<ans/n/2;//一个多边形按照顺时针顺序有n个排列表示，逆时针也有n个，所以要除以2n
	return 0;
}