【BZOJ】4558: [JLoi2016]方

时间:2024-09-27 18:33:44

【题意】给定有(n+1)*(m+1)个点的网格图,其中指定k个点不合法,求合法的正方形个数(四顶点合法)。

【算法】计数

【题解】斜着的正方形很麻烦,所以考虑每个斜正方形其外一定有正的外接正方形。

也就是,一个边长为x的正放的正方形,同时代表x个正方形(其中1~x-1为斜正方形)

num0:首先计算所有点合法时全图的正方形个数。

枚举长度i,则num0=∑i*(n-i+1)*(m-i+1)。(长度为i的情况下,左上角多大的矩形能作为左上端点)

num1:减去单个不合法点构成的正方形

对于一个不合法点有四个方向,任意一个方向可以视为calc(l,r,h),l为向左延伸长度,r为向右,h为向上。

包含斜放的正方形在内,也就是一条线段只要接触到该点就会有一个该点构成的正方形。

考虑长度为1的情况是(0,1)(1,0),长度为2是(0,2)(1,1)(2,0),随长度递增答案有以下规律,只要判断h在哪个区间就可以快速计算答案:

当长度为0,答案为0。

当长度为1~min(l,r),数列递增,答案为(h+3)*h/2。

当长度为min(l,r)+1~max(l,r),数列为常数min(l,r)+1,答案为(min+3)*min/2+(h-min)*(min+1)。(一边受限)

当长度为max(l,r)+1~min(l,r)+max(l,r),数列递减,答案为(min+3)*min/2+(max-min)*(min+1)+(min*2+1-h+max)*(h-max)/2。(两边受限)

当长度为min+max+1~+∞,答案为(min+3)*min/2+(max-min)*(min+1)+(min+1)*min/2

细心推一推就可以了。

num2:加上两个不合法点构成的正方形

枚举两个不合法点(A,B)(C,D)的连边,有两种情况:

作为边:另外两个点是(A+D-B,B+A-C)(C+D-B,D+A-C),或另一方向的(A+B-D,B+C-A)(C+B-D,D+C-A)。

作为对角线,利用全等三角形解方程可得,另外两个点是((A-D+B+C)/2,B+C-(A-D+B+C)/2)((A-B+D+C)/2,A+D-(A-B+D+C)/2)。

判断另外两个点是否整点和是否在界内。

num3:减去三个不合法点构成的正方形

在枚举计算num2的时候可以顺便求得(二分另外两个点判断是否是不合法点),当然这样每三个点会被计算3次,除以三即可。

注意,每三个点构成了一个正方形时都应该统计一次,这样粗糙的统计才是容斥的基础。(手算一下就可以得知了)

num4:加上四个不合法点构成的正方形

计算num2时顺便求得,这样每四个点会被计算6次,除以6即可。

综上所述,ans=num0-num1+num2-num3+num4。

注意一些细节,如fabs(x-(int)(x+eps))<=eps。

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
#define ll long long
#define lowbit(x) x&-x
using namespace std;
int read(){
char c;int s=,t=;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a<b?b:a;}
int ab(int x){return x>?x:-x;}
//int MO(int x){return x>=MOD?x-MOD:x;}
//void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
/*------------------------------------------------------------*/
const int inf=0x3f3f3f3f,maxn=,MOD=1e8+,maxk=;
const double eps=1e-;
int n,m,kind,ans=,two,three,four;
struct cyc{
int x,y;
bool operator < (const cyc &a)const{
return x<a.x||(x==a.x&&y<a.y);
}
}a[maxk],p1,p2;
int MO(int x){return x>=MOD?x-MOD:x;}
int calc(ll l,ll r,ll h){
ll H,num=,mins=min(l,r),maxs=max(l,r);
if(h>mins)H=mins;else H=h;
num+=(H+)*H/;
if(h<=mins)return num%MOD; if(h>maxs)H=maxs;else H=h;
num+=(H-mins)*(mins+);
if(h<=maxs)return num%MOD; if(h>mins+maxs)H=mins+maxs;else H=h;
num+=(mins*+-H+maxs)*(H-maxs)/;
return num%MOD;
}
void check(){
if(p1.x<||p1.x>n||p2.x<||p2.x>n||p1.y<||p1.y>m||p2.y<||p2.y>m)return;
two++;
int x=lower_bound(a+,a+kind+,p1)-a;
bool o1=x>=&&x<=kind&&(a[x].x==p1.x&&a[x].y==p1.y);
x=lower_bound(a+,a+kind+,p2)-a;
bool o2=x>=&&x<=kind&&(a[x].x==p2.x&&a[x].y==p2.y);
if(o1)three++;if(o2)three++;if(o1&&o2)four++;
}
bool T(double x){return fabs(x-(int)(x+eps))<=eps;}
int main(){
n=read();m=read();kind=read();
for(int i=;i<=min(n,m);i++){
ans=MO(ans+1ll*(n-i+)*(m-i+)%MOD*i%MOD);
}
for(int i=;i<=kind;i++){
a[i].x=read();a[i].y=read();
int num=;
num=MO(num+calc(a[i].x,n-a[i].x,a[i].y));
num=MO(num+calc(a[i].x,n-a[i].x,m-a[i].y));
num=MO(num+calc(a[i].y,m-a[i].y,a[i].x));
num=MO(num+calc(a[i].y,m-a[i].y,n-a[i].x));
num=MO(num+MOD-min(a[i].x,a[i].y)-min(a[i].x,m-a[i].y)-min(n-a[i].x,a[i].y)-min(n-a[i].x,m-a[i].y));
ans=MO(ans+MOD-num);
}
sort(a+,a+kind+);
two=;three=;four=;
for(int i=;i<kind;i++){
for(int j=i+;j<=kind;j++){
int A=a[i].x,B=a[i].y,C=a[j].x,D=a[j].y;
p1=(cyc){A+D-B,B+A-C};p2=(cyc){C+D-B,D+A-C};
check();
p1=(cyc){A+B-D,B+C-A};p2=(cyc){C+B-D,D+C-A};
check();
if(T(1.0*(A+B+C-D)/)&&T(1.0*(A-B+D+C)/)){
p1=(cyc){(A-D+B+C)/,B+C-(A-D+B+C)/};p2=(cyc){(A-B+D+C)/,A+D-(A-B+D+C)/};
check();
}
}
}
ans=MO(ans+two);
ans=MO(ans+MOD-three/);
ans=MO(ans+four/);
printf("%d",(ans%MOD+MOD)%MOD);
return ;
}