cjb-poi2010sheep

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <stack>
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
struct poi
{
    int x,y;
    friend poi operator -(poi x,poi y)
    {
        return (poi){x.x-y.x,x.y-y.y};
    }
    friend int operator *(poi x,poi y)
    {
        return x.x*y.y-y.x*x.y;
    }
    void read()
    {
        scanf("%d%d",&x,&y);
    }
}a[700],b[21000],st;
bool cmp(poi a,poi b){ return (a-st)*(b-st)<0; }
bool cut[700][700];
int f[700][700];
int n,m,mod;
int dfs(int l, int r)
{
    if (f[l][r]!=-1)return f[l][r];
    if (l+1==r)return f[l][r]=1;
    f[l][r]=0;
    for(int k=l+1;k<r;k++)
        if (cut[l][k] && cut[k][r])f[l][r]=(1ll*f[l][r]+1ll*dfs(l,k)*dfs(k,r)%mod)%mod;
    return f[l][r];
}
int main()
{
    cin>>n>>m>>mod;
    rep(i,n)a[i].read();
    rep(i,m)b[i].read();
    st=a[1];
    sort(a+2,a+n+1,cmp);
    rep(i,n-1)
    {
        st=a[i];
        sort(b+1,b+m+1,cmp);
        int now=0;
        for(int j=i+1;j<=n;j++)
        {
            while (now<m && (b[now+1]-st)*(a[j]-st)<=0)++now;
            if (now&1 || (b[now]-st)*(a[j]-st)==0)continue;
            cut[i][j]=cut[j][i]=1;
        }
    }
    memset(f,255,sizeof(f));
    cout<<dfs(1,n)<<endl;
}
}}}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <stack>
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
struct poi
{
    int x,y;
    friend poi operator -(poi x,poi y)
    {
        return (poi){x.x-y.x,x.y-y.y};
    }
    friend int operator *(poi x,poi y)
    {
        return x.x*y.y-y.x*x.y;
    }
    void read()
    {
        scanf("%d%d",&x,&y);
    }
}a[700],b[21000],st;
bool cmp(poi a,poi b){ return (a-st)*(b-st)<0; }
bool cut[700][700];
int f[700][700];
int n,m,mod;
int dfs(int l, int r)
{
    if (f[l][r]!=-1)return f[l][r];
    if (l+1==r)return f[l][r]=1;
    f[l][r]=0;
    for(int k=l+1;k<r;k++)
        if (cut[l][k] && cut[k][r])f[l][r]=(1ll*f[l][r]+1ll*dfs(l,k)*dfs(k,r)%mod)%mod;
    return f[l][r];
}
int main()
{
    cin>>n>>m>>mod;
    rep(i,n)a[i].read();
    rep(i,m)b[i].read();
    st=a[1];
    sort(a+2,a+n+1,cmp);
    rep(i,n-1)
    {
        st=a[i];
        sort(b+1,b+m+1,cmp);
        int now=0;
        for(int j=i+1;j<=n;j++)
        {
            while (now<m && (b[now+1]-st)*(a[j]-st)<=0)++now;
            if (now&1 || (b[now]-st)*(a[j]-st)==0)continue;
            cut[i][j]=cut[j][i]=1;
        }
    }
    memset(f,255,sizeof(f));
    cout<<dfs(1,n)<<endl;
}