方

题目大意

给出一个 \(n\) 行 \(m\) 列的矩阵，每行的格点从上到下依次编号为 \(0\) 到 \(n\) ，每列的格点从左到右依次编号为 \(0\) 到 \(m\) 。

选出四个不同的格点，可以组成一个四边形，问有多少种不同的选法，能够组成一个正方形。

由于出题人太害怕你做出这道题，于是他从这个矩阵中删去了 \(k\) 个点，这 \(k\) 点将不能被选择。

分析

容斥

首先，必须注意此处的正方形可能是斜着摆放的。

然后我们可以考虑容斥。

若设 \(f_i\) 表示至少有 \(i\) 个顶点为坏点的正方形有多少种。

那么， \(ans=f_0-f_1+f_2-f_3+f_4\) 。

\(f_0\)

对于 \(f_0\) 的情况，事实上，即是假设所有点都是好点的情况。

我们发现，对于正着摆放的正方形，事实上，我们是不难求解的。看起来比较难处理的是斜着摆放的正方形，我们可以把它画出来。

我们发现，对于任何一个斜着摆放的正方形，我们都是能够画出一个正着摆放的正方形恰好把他框住，换句话来说，对于任何一个正着摆放的正方形，我们都能够在它的内部画出若干个斜着摆放的正方形。

那么我们就成功的把问题转化为了求解对于一个边长为 \(x\) 的正着摆放的正方形，会产生多少的贡献。

仔细观察上图，我们发现，确定一条边，从上面的任意一个格点，我们都是能够唯一确认一个正方形，这不难理解，有点类似于里面的正方形缓慢旋转的过程，在这个过程中我们需要维持的是四个角落形成的三角形全等，则每次移动会带动另外一条边上的顶点移动，刚好能够移动 \(x-1\) 次，再加上正着摆放的正方形本身，对于这样一个正方形，产生的贡献事实上就是 \(x\) 。

运用我们成功得到的这个结论，则：

\[f_0=\sum_{i>=1}^{i<=min(n,m)} i\times (n-i+1)\times (m-i+1) \]

\(f_1\)

接下来我们需要解决更复杂的正方形上至少有一个坏点的情况。

我们可以考虑枚举所有坏点 ，单独考虑每个坏点产生的贡献。

如图，我们从每个坏点建立一个坐标系。

首先，我们仍然先考虑这是一个正着摆放的正方形，则我们可以从这个坏点向四个方向分别延伸，变成逐渐扩大，最后得到的贡献不难求得。

那么对于斜着摆放的正方形了？上一个小问题中，我们知道了对于一个边长为 \(x\) 的正方形，从它边上的一个点出发，可以唯一确定一个正方形。

则我们又成功的将问题转化为，求有多少个正着的正方形的边上，会存在这个坏点，产生的贡献即是这种正方形的个数，由于我们前面考虑了在正着摆放的正方形顶点上的情况，所以接下来不考虑这个坏点是正着摆放正方形的顶点。

(图中的线段表示枚举的正方形的边长)

接下来，我们逐步考虑边长的情况。

首先，不失一般性的假设，\(x<y\) 。

显然，边长最小为 \(2\) ，即线段 \(1\) ，我们考虑将线段 \(1\) 逐步延伸，发现没增加 \(1\) ，对应的方案数也会增加 \(1\) ，缓慢向上延伸，直到边长为 \(x+1\) 时，方案数达到最大值，即我们的线段 \(2\) 。

之后，我们每一次扩大边长，实际上线段 \(2\) 能够向下移动的总步数也即是我们的总方案数不会变化进一步变化，始终维持在某个值上。

当达到 \(y+2\) 时，再次出现变化，也即是我们的线段 \(3\) 的下一次扩大，我们发现，这会让我们上移的步数也即是我们的方案数减少 \(1\) ，这个变化将持续到 \(x+y\) 也即是我们将整个正方形抵满。

我们的贡献最后其实形成了一个函数，大概长成这样：

第一段，如果能够完全取到，即为 \(\frac{x\times(x+1)}{2}\) 。

第二段，如果能够完全取到，即为 \(x\times(y-x)\) 。

第三段，如果能够完全取到，即为 \(\frac{x\times (x-1)}{2}\) 。

注意这里说的是完全取到，什么时候不能完全取到，即不存在这个区间或者说目前取到的边长事实上已经超过了 \(L\) 的时候我们不能将这个区间的贡献全部一股脑的弄上去。

综上，如果设我们上述的函数为 \(Get(x,y,z)\) ，该坏点距离上边界的距离为 \(u\) ，下边界的距离为 \(d\) ，左边界的距离为 \(l\) ，右边界的距离为 \(r\) ，则：

\[f_1=min(u,r)+min(r,d)+min(d,l)+min(u,l)+Get(u,d,l)+Get(u,d,r)+Get(l,r,u)+Get(l,r,d) \]

\(f_2\)

到这里我们终于可以开始求 \(f_2\) 了。

首先，如果我们确定了两个坏点，事实上，我们就已经可以把这两个坏点能够形成的正方形给求解出来了。

具体如下图：

通过向量的知识或者其他的一些方法，我们能够求出其他两个点的坐标，这里就不再赘述了，属于是数学知识了。

求出另外两个点的坐标后，首先要注意这两个坐标可能不在格点上，对于这种我们是需要舍掉的。

然后再观察。

显然没有人想要再去求一下 \(f_3\) ，\(f_4\) ，有没有什么神奇的方法能把这两个东西删去。实际上是有的，我们可以手动给我们每个正方形的贡献加上一个系数。

具体可以举个例子说明。

假设，这个正方形上有三个坏点。

那其实，在 \(f_0\) 中，它被计算了 \(+1\) 次，在 \(f_1\) 中，由于每一个坏点都要确定一次它，它被计算了 \(-3\) 次，显然，我们期望 \(f_2\) 中，让它被计算 \(+2\) 次。

正好，我们是可以确定这个正方形的，换句话来说，我们能够确定这个正方形上的坏点个数，于是乎，我们能够“智能的”给他安排一个系数。

但是 \(f_2\) 本身中也有可能是会重复的，就像 \(f_1\) 一样，每两组会重复确定他一次，我们必须想办法规避这个问题，我们想到了给每个坏点打上一个编号，只要当这两个坏点确定出的正方形中，它们是编号最大的两个坏点时，我们才计算贡献，这样，我们就有效的规避了这个问题。

时间复杂度

求解 \(f_0\) 与 \(f_1\) 的时间复杂度都比较小，我们主要谈一谈求解 \(f_2\) 时的一些问题。

如果用 \(map\) 实现 \(f_2\) 中的一些操作，显然我们求 \(f_2\) 的复杂度是 \(O(k^2logn)\) 的，看起来非常可过，但其实应该是过不了的(指洛谷)，当然如果你常数小肯定也能过。我们需要优化这个 \(log\) ，要么用 \(unorderedmap\) ，要么使用离散化，都可以去掉这个 \(log\) 。

CODE

#include <bits/stdc++.h>
#include <unordered_map>
#define int long long
using namespace std;
const int N=1e5+10,M=2e3+10,MOD=1e8+7;
namespace IO {
int len = 0;
char ibuf[(1 << 20) + 1], *iS, *iT, out[(1 << 25) + 1];
#define gh()                                                                   \
  (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin),         \
   (iS == iT ? EOF : *iS++) : *iS++)
inline int read() {
  char ch = gh();
  int x = 0;
  char t = 0;
  while (ch < '0' || ch > '9')
    t |= ch == '-', ch = gh();
  while (ch >= '0' && ch <= '9')
    x = x * 10 + (ch ^ 48), ch = gh();
  return t ? -x : x;
}
inline void putc(char ch) { out[len++] = ch; }
template <class T> inline void write(T x) {
  if (x < 0)
    putc('-'), x = -x;
  if (x > 9)
    write(x / 10);
  out[len++] = x % 10 + 48;
}
string getstr(void) {
  string s = "";
  char c = gh();
  while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)
    c = gh();
  while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF))
    s.push_back(c), c = gh();
  return s;
}
void putstr(string str, int begin = 0, int end = -1) {
  if (end == -1)
    end = str.size();
  for (int i = begin; i < end; i++)
    putc(str[i]);
  return;
}
inline void flush() {
  fwrite(out, 1, len, stdout);
  len = 0;
}
} // namespace IO
using IO::flush;
using IO::getstr;
using IO::putc;
using IO::putstr;
using IO::read;
using IO::write;

struct node{
	int x,y;
}p[M];
struct pair_hash
{
    template<class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2>& p) const
    {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        return h1 ^ h2;
    }
};

unordered_map<pair<int, int>, int, pair_hash> mp;
int n,m,k,cnt,ans;
inline bool cmp(node a,node b) { return a.y<b.y; }
inline int Get_val(int x,int y,int L)
{
	int res=0;
	if(x>y) swap(x,y);
//	if(2<=x+1){
		if(L<2) return 0;
		else if(L>x+1) res=(res+((x+1)*x)/2)%MOD;
		else return (L*(L-1))/2; //令x+1=L，则x=L-1
//	}
//	if(x+2<=y+1){
		if(L>y+1) res=(res+x*(y-x))%MOD; //超出，加贡献
		else return (res+(L-x-1)*x)%MOD; //令y+1=L
//	}
//	if(y+2<=x+y){
		if(L>x+y) return (res+(x*(x-1))/2)%MOD;
		else return (res+(2*x+y-L)*(L-y-1)/2)%MOD; //令x+y=L,则x=L-y
//	}
}
signed main()
{
//	while(1){
//		int x=read(),y=read(),z=read();
//		printf("%lld\n",Get_val(x,y,z));
//	}
	n=read(),m=read(),k=read();
	for(register int i=1;i<=k;i++){
		pair<int,int> add;
		p[i].x=read(),p[i].y=read();
		add.first=p[i].x,add.second=p[i].y;
		mp[add]=++cnt;
	}
	for(register int i=1;i<=min(n,m);i++) ans=(ans+i*(n-i+1)%MOD*(m-i+1)%MOD)%MOD;
	//sort(p+1,p+k+1,cmp);
	for(register int i=1;i<=k;i++){
		for(register int j=i+1;j<=k;j++){ //枚举正方形
			pair<int,int> a,b;
			a.first=p[i].x,a.second=p[i].y;
			b.first=p[j].x,b.second=p[j].y;
			//printf("%d %d %d %d\n",a.first,a.second,b.first,b.second);
			int v=min(mp[a],mp[b]);
			int temp,sum;
			int x1=p[i].y,y1=n-p[i].x,x2=p[j].y,y2=n-p[j].x;
			//printf("%d %d %d %d\n",x1,y1,x2,y2);
			int ny=x2-x1,nx=abs(y2-y1);
			//printf("%d %d\n",nx,ny);
			if(y2>y1) ny*=-1;
			pair<int,int> p1,p2;
			//第一个正方形的两个新点
			p1.first=n-(ny+y1),p1.second=nx+x1;
			p2.first=n-(ny+y2),p2.second=nx+x2;
			//printf("%d %d %d %d\n",p1.first,p1.second,p2.first,p2.second);
			if(p1.first>=0&&p1.second>=0&&p1.first<=n&&p1.second<=m){
				if(p2.first>=0&&p2.second>=0&&p2.first<=n&&p2.second<=m){
					temp=0,sum=0;
					if(mp.find(p1)!=mp.end()) temp=max(mp[p1],temp),++sum;
					if(mp.find(p2)!=mp.end()) temp=max(mp[p2],temp),++sum;
					if(v>temp) ans=(ans+sum+1)%MOD;
				}
			}
			//第二个正方形的两个新点
			nx=-nx,ny=-ny;
			p1.first=n-(ny+y1),p1.second=nx+x1;
			p2.first=n-(ny+y2),p2.second=nx+x2;
			if(p1.first>=0&&p1.second>=0&&p1.first<=n&&p1.second<=m){
				if(p2.first>=0&&p2.second>=0&&p2.first<=n&&p2.second<=m){
					temp=0,sum=0;
					if(mp.find(p1)!=mp.end()) temp=max(mp[p1],temp),++sum;
					if(mp.find(p2)!=mp.end()) temp=max(mp[p2],temp),++sum;
					if(v>temp) ans=(ans+sum+1)%MOD;
				}
			}
			//第三个正方形的两个新点
			//if((x2-x1)*(y2-y1)==0) continue; //
			nx=-nx,ny=-ny;
			double dx=((x2-x1)/2.0-nx/2.0),dy=((y2-y1)/2.0-ny/2.0);
			if((double)(dx-(int)dx)||(double(dy-(int)dy))) continue; //该正方形不存在
			p1.first=n-(ny+dy+y1),p1.second=nx+dx+x1;
			p2.first=n-(dy+y1),p2.second=dx+x1;
			if(p1.first>=0&&p1.second>=0&&p1.first<=n&&p1.second<=m){
				if(p2.first>=0&&p2.second>=0&&p2.first<=n&&p2.second<=m){
					temp=0,sum=0;
					if(mp.find(p1)!=mp.end()) temp=max(mp[p1],temp),++sum;
					if(mp.find(p2)!=mp.end()) temp=max(mp[p2],temp),++sum;
					if(v>temp) ans=(ans+sum+1)%MOD;
				}
			}
		}
	}
	//cout<<ans<<"\n";
	for(register int i=1;i<=k;i++){
		int u,d,l,r;
		u=p[i].x,d=n-p[i].x,l=p[i].y,r=m-p[i].y;
		int temp=(min(u,r)+min(r,d)+min(d,l)+min(u,l))%MOD;
		ans=((ans-temp)%MOD+MOD)%MOD;
		ans=((ans-Get_val(u,d,l))%MOD+MOD)%MOD;
		ans=((ans-Get_val(u,d,r))%MOD+MOD)%MOD;
		ans=((ans-Get_val(l,r,u))%MOD+MOD)%MOD;
		ans=((ans-Get_val(l,r,d))%MOD+MOD)%MOD;
	}
	printf("%lld\n",ans);
	return 0;
}