我又TM没看题,题面只要求四个顶点不是坏点就好了(导致我纠结了1天)!!!

观察到$K$挺小的,就想办法搞些事情。

之后想到容斥,$f_i$表示至少有$i$个顶点是坏点。

答案就为$f_0-f_1+f_2-f_3+f_4$

对于同样大小的,且中心点为同一处的非横平竖直正方形而言,一定有一个最小的(横平竖直)正方形能包裹住这些正方形,且只有一个,如下图

11.PNG

对于这个最小的(横平竖直)正方形而言,内含其边长$l$$-1$个正方形,算上其本身,就有$l$个正方形。

思考一下,对于$(n+1,m+1)$的地图而言,有多少个这样的边长为$l$的中心点?

有$(n-l+1)*(m-l+1)$个。

因此对于边长为$l$的中心点的来说,对$f_0$的贡献为$(n-l+1)*(m-l+1)*l$

因此$f_0=\sum\limits _{i=1}^{\min(n,m)}(n-i+1)*(m-i+1)*i$

难点就在于如何计算$f_1$

考虑一个坏点$(x,y)$,大概是这样的:

12.PNG

蓝色区域就是$(n+1)*(m+1)$的地图, $P$为原点分成上、下、左、右四个半平面进行计算。

这里单独对于上平面进行计算

13.PNG

即$l$为$p$到左边界的距离,$r$为$p$到右边界的距离,$h$同理。

最大的正方形边长不超过$t=\min(l+r,h)$。

现在考虑以点$p$为顶点的正方形如何计算(这一部分是我曾经最不懂的地方,尽量给读者讲懂吧)。

对于非横平竖直的正方形如何转化?

14.PNG
还记得第一张图吗?对于这个正方形,可以套上一个最小的横平竖直的正方形来表示它,也就是这样:

15.PNG

关于这个的正确性,从第一张图可以明显得知,它是唯一的。

之后就是统计这些横平竖直的正方形有多少个。

如果不考虑限制的话。

答案就是$\sum\limits_{i=1}^{\min(l+r,h)}i+1=\frac{t*(t+3)}{2}$

减去不合法的,这里稍微解释一下,

对于$t>l$的部分,结合图来理解一下(这个图大的好像画错了,不过没关系)

16.PNG

大概可以糊出不合法的方案就是$\frac{(t-l)*(t-l+1)}{2}$

对于$r$也来一下。

统计完四个方向之后,发现真正的横平竖直(也就是以$p$为顶点,且边在格子上)的正方形会算重,所以要去重。

之后$f_2,f_3,f_4$差不多少一个套路,都是随便枚举两个坏点,判断是否合法,然后通过垂直向量算出剩下两点是否合法。

需要注意的就是枚举这两点连线是对角线还是边。

$f_3$,由于三个点,任意枚举两个点,会重复2次,因此$/3$

$f4$,同理,$/6$

$\operatorname{The ~End}$

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int M=570707,N=2005,mod=1e8+7;
const double pi=acos(-1);
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int n,m,t;
struct Hashmap
{
    struct node{int x,y,next;}a[M<<1];int len,last[mod];
    void ins(int i,int j)
    {
        int x=1ll*i*(m+1)*j%M;
        for(int k=last[x];k;k=a[k].next)
            if(a[k].x==i&&a[k].y==j)return ;
        a[++len]=(node){i,j,last[x]};last[x]=len;
    }
    bool pd(int i,int j)
    {
        int x=1ll*i*(m+1)*j%M;
        if(!last[x])return 0;
        for(int k=last[x];k;k=a[k].next)
            if(a[k].x==i&&a[k].y==j)return 1;
        return 0;
    }
}H;
struct node
{
    int x,y;
    node(int x=0,int y=0):x(x),y(y){}
    bool operator <(const node a)const{return x==a.x?y<a.y:x<a.x;}
    node operator -(const node a)const{return node(x-a.x,y-a.y);}
    node operator +(const node a)const{return node(x+a.x,y+a.y);}
    node operator *(const int a)const{return node(x*a,y*a);}
    node operator /(const int a)const{return node(x/a,y/a);}
    inline node sap(){return node(y,-x);}
    inline bool even(){return (!(x&1))&&(!(y&1));}
}pt[N];
inline bool pdnode(node a){return 0<=a.x&&a.x<=n&&0<=a.y&&a.y<=m;}
bool legal(node a,node b){return pdnode(a)&&pdnode(b);}
bool broke(node a){return H.pd(a.x,a.y);}
inline ll calc0(int n,int m)
{
    ll sum=0;int lim=min(n,m);
    for(int i=1;i<=lim;i++)sum=(sum+1ll*i*(n-i+1)*(m-i+1))%mod;
    return sum;
}
inline ll calc(int l,int r,int h)
{
    ll t=min(l+r,h);
    if(!t)return 0;
    ll sum=t*(t+3)/2%mod;
    if(t>l)sum-=(t-l)*(t-l+1)/2%mod;
    if(t>r)sum-=(t-r)*(t-r+1)/2%mod;
    return (sum%mod+mod)%mod;
}
inline ll calc1(int x,int y)
{
    int a=n-x,b=m-y,c=x,d=y;
    ll sum=(calc(b,d,c)+calc(b,d,a)+calc(a,c,b)+calc(a,c,d))%mod;
    sum-=(min(a,b)+min(b,c)+min(c,d)+min(d,a));
    return (sum%mod+mod)%mod;
}
inline ll calc2(node a,node b)
{
    node tg=(a-b).sap();int sum=0;
    if(legal(a+tg,b+tg))sum++;
    if(legal(a-tg,b-tg))sum++;
    node mid=a+b,c=mid+tg,d=mid-tg;
    if(c.even()&&d.even()&&legal(c/2,d/2))sum++;
    return sum;
}
inline ll calc3(node a,node b)
{
    node tg=(a-b).sap();int sum=0;
    if(legal(a+tg,b+tg))sum+=broke(a+tg)+broke(b+tg);
    if(legal(a-tg,b-tg))sum+=broke(a-tg)+broke(b-tg);
    node mid=a+b,c=mid+tg,d=mid-tg;
    if(c.even()&&d.even()&&legal(c/2,d/2))sum+=broke(c/2)+broke(d/2);
    return sum;
}
inline ll calc4(node a,node b)
{
    node tg=(a-b).sap();int sum=0;
    if(legal(a+tg,b+tg))sum+=broke(a+tg)&&broke(b+tg);
    if(legal(a-tg,b-tg))sum+=broke(a-tg)&&broke(b-tg);
    node mid=a+b,c=mid+tg,d=mid-tg;
    if(c.even()&&d.even()&&legal(c/2,d/2))sum+=broke(c/2)&&broke(d/2);
    return sum;
}
int main()
{
    qr(n),qr(m),qr(t);
    for(int i=1;i<=t;i++)qr(pt[i].x),qr(pt[i].y),H.ins(pt[i].x,pt[i].y);
    ll f0=0,f1=0,f2=0,f3=0,f4=0;f0=calc0(n,m);
    for(int i=1;i<=t;i++)f1+=calc1(pt[i].x,pt[i].y);
    for(int i=1;i<=t;i++)for(int j=i+1;j<=t;j++)
    {
        f2+=calc2(pt[i],pt[j]),f3+=calc3(pt[i],pt[j]);f4+=calc4(pt[i],pt[j]);
    }
    f3/=3;f4/=6;
    ll ans=((f0-f1+f2-f3+f4)%mod+mod)%mod;
    qw(ans);puts("");
    return 0;
}