题解 P3504 【[POI2010]OWC-Sheep】
xtx1092515503
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```。
代码：
```cpp
#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;
}
```