/*
上帝说 要方
是的 很方
计数问题的容斥思想 (首先要注意 正方形有斜着的QAQ)
考虑我们要求的合法正方形 ans 根据容斥
ans = 无限制方案书 - 一个点确定的方案数 + 两个点确定的方案数 - 三个点确定的方案数 + 四个点确定的方案数 无限制方案数:
首先假设我们选择了一个n * n的正方形
那么这个正方形就包含了 n - 1种边界在正方形边上的正方形 根据这个来求出总方案数 一个点确定的方案数:(from huanghongxun's blog)
考虑每个被删除的点,其对上半,左半,右半,下半部分的影响类似,重复计算的就是正着的正方形的个数,即长宽的较小值。
用(l,r,h)(l,r,h)表示一个区域,删除的点在底边界上,左边有l个坐标,右边有r个坐标。
考虑(6+6)*6的区域。
倾斜0格的有6个,1格的有5个,2格的有4个,……,5格的有1个,6格的有6个,总的是27个。
如果是(6+6)*5的区域,那么就是5,4,3,2,1,5了。
如果是(2+2)*5的区域,那么就是2,2,2,2。
令z=min{l+r,h}z=min{l+r,h}
我们先假设高度要不大于左右侧,那么此时的答案就是z(z+3)/2。
如果大于了左右侧,那么考虑减去多计算的部分,如果左右侧补全到z,那么多出来的部分即n=z?l或z?rn=z?l或z?r,公式即为n(n+1) /2。
两个点确定的方案数:
三个点确定的方案数:
四个点确定的方案数:
这三个可以枚举两个已经确定的点, 然后算出剩下的两个点进行计算
确定三个的 除以3 确定四个的 除以6
愉快地解决
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#include<iostream>
#define ll long long
#define M 5100
const int mod = ;
using namespace std;
struct P {
int x,y;
bool operator < (const P &b) const {
return x == b.x ? y < b.y: x < b.x;
}
} note[M],a,b;
int read() {
int nm = , f = ;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f= -;
for(; isdigit(c); c = getchar()) nm = nm * + c - '';
return nm * f;
}
ll ans = , n, m, k, cnt3, cnt4;
set<P>st;
ll wk1(int l, int r, int h) {
int z = min(l + r, h);
if(z == ) return ;
ll zz = 1ll * z * (z + ) / ;
if(z > l) zz -= 1ll * (z - l) * (z - l + ) / ;
if(z > r) zz -= 1ll * (z - r) * (z - r + ) / ;
return zz;
} void solve1() {
for(int i = ; i <= k; i++) {
int x = note[i].x, y = note[i].y, l = x, r = n - x, u = y, d = m - y;
ans -= (wk1(l,r,u) + wk1(l,r,d) + wk1(u,d,l) + wk1(u,d,r) - min(l, u) - min(l, d) - min(r, u) - min(r, d));
ans %= mod;
}
} void wk2(P a, P b) {
if(a.x < || a.x > n || b.x < || b.x > n || a.y < || b.y < || a.y > m || b.y > m) return;
ans++;
int op = st.count(a) + st.count(b);
if(op == ) cnt3++;
if(op == ) cnt3 += , cnt4++;
} void solve234() {
for(int i = ; i <= k; i++) {
a = note[i];
for(int j = i + ; j <= k; j++) {
b = note[j];
int dx = a.x - b.x, dy = a.y - b.y, xx, yy;
/*两点相邻的*/
wk2((P){a.x + dy, a.y - dx}, (P){b.x + dy, b.y - dx});
wk2((P){a.x - dy, a.y + dx}, (P){b.x - dy, b.y + dx});
if((abs(dx) + abs(dy)) & ) continue;
/*对角线的*/
xx = dx - dy >> , yy = dx + dy >> ;
wk2((P){a.x - xx, a.y - yy}, (P){b.x + xx, b.y + yy});
}
}
} int main() {
n = read(), m = read(), k = read();
for(int i = ; i <= k; i++) {
note[i].x = read(), note[i].y = read();
st.insert(note[i]);
}
for(int i = ; i <= min(n, m); i++) ans += 1ll * i * (n - i + ) * (m - i + ), ans %= mod;
solve1();
solve234();
ans -= cnt3 / - cnt4 / ;
cout << ((ans % mod) + mod) % mod;
return ;
}
04-25 10:42