自动搬运

查看原文

来自洛谷，原作者为

	xtx1092515503 Mathematics compares the most diverse phenomena, and discovers the secret analogies which unite them. @Joseph Fourier

搬运于2025-08-24 21:49:37，当前版本为作者最后更新于2020-11-28 14:27:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

本题要么用int判叉积大小，要么乖乖开long double，double精度不够。

卡了我大半个月啊。

首先，如果没有羊的限制，那么DP是很好想的，就是一个多边形三角剖分问题。设 $f[i,j]$ 表示区间 $[i,j]$ 的剖分数量，则有

$$f[i,j]=\begin{cases}1&(j-i\leq 1,\text{状态合法})\\\sum\limits_{k=i+1}^{j-1}f[i,k]f[k,j]&(j-i>l,\text{状态合法})\\0&(\text{状态不合法})\end{cases} $$

下面就考虑一下哪些是合法状态。这个就可以通过枚举 $i$，然后将其它所有顶点和羊以 $i$ 为原点进行极角排序，然后就可以看两个顶点间有多少只羊（即判断状态是否合法了）。

这里我有点后悔使用了atan2函数，因为坐标范围很大，如果这样排序就需要很大的精度，最终把eps是设成了1e-20才过。并且，我在排序的过程中使用了fmod函数，本意是把所有点映射到 $[0,\pi)$ 范围中，却没想到fmod函数的结果可能为负（这一点和%符号一模一样）然后就挂掉了。最后不得不手写了fmod。

代码：

#include<bits/stdc++.h>
using namespace std;
#define double long double
const double pi=acos(-1);
const double eps=1e-20;
int n,m,mod,f[610][610];
struct Vector{
	int x,y;
	Vector(int X=0,int Y=0){x=X,y=Y;}
	friend Vector operator +(const Vector &u,const Vector &v){return Vector(u.x+v.x,u.y+v.y);}
	friend Vector operator -(const Vector &u,const Vector &v){return Vector(u.x-v.x,u.y-v.y);}
	friend Vector operator *(const Vector &u,const int &v){return Vector(u.x*v,u.y*v);}
	friend Vector operator /(const Vector &u,const int &v){return Vector(u.x/v,u.y/v);}
	friend int operator &(const Vector &u,const Vector &v){return u.x*v.y-u.y*v.x;}//cross times
	friend int operator |(const Vector &u,const Vector &v){return u.x*v.x+u.y*v.y;}//point times
	double operator ~()const{return atan2(y,x);}
	void read(){scanf("%d%d",&x,&y);}
	void print(){printf("(%d,%d)",x,y);}
}p[610],q[20100];
double r[20100];
bool bad[610][610];
int dfs(int l,int r){
	if(r-l<=2)return 1;
	if(f[l][r]!=-1)return f[l][r];
	f[l][r]=0;
	for(int i=l+1;i<=r-1;i++)if(!bad[l][i]&&!bad[i][r])(f[l][r]+=1ll*dfs(l,i)*dfs(i,r)%mod)%=mod;
	return f[l][r];
}
double FMOD(double x){
	if(x<0)x+=2*pi;
	if(x>=2*pi)x-=2*pi;
	return x;
}
int main(){
	scanf("%d%d%d",&n,&m,&mod),memset(f,-1,sizeof(f));
	for(int i=1;i<=n;i++)p[n-i].read();
	for(int i=0;i<m;i++)q[i].read();
	for(int i=0;i+1<n;i++){
		double theta=~(p[i+1]-p[i])-eps;
		for(int j=0;j<m;j++)r[j]=FMOD(~(q[j]-p[i])-theta);
		sort(r,r+m);
//		for(int j=0;j<m;j++)printf("%.20Lf ",r[j]);puts("");
		for(int j=i+1,k=0;j<n;j++){
			double now=FMOD(~(p[j]-p[i])-theta);
			while(k<m&&now>r[k])k++;
//			printf("%d %d:%d\n",i,j,k);
//			printf("%.20Lf\n",now);
			if((k&1)||(k<m&&fabs(now-r[k])<eps)||(k&&fabs(now-r[k-1])<eps))bad[i][j]=true;
		}
	}
//	for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)printf("[%d,%d]:%d\n",i,j,bad[i][j]);
	printf("%d\n",dfs(0,n-1));
	return 0;
}