首页 > 代码库 > bzoj4558: [JLoi2016]方
bzoj4558: [JLoi2016]方
Description
上帝说，不要圆，要方，于是便有了这道题。由于我们应该方，而且最好能够尽量方，所以上帝派我们来找正方形
上帝把我们派到了一个有N行M列的方格图上，图上一共有(N+1)×(M+1)个格点，我们需要做的就是找出这些格点形
成了多少个正方形（换句话说，正方形的四个顶点都是格点）。但是这个问题对于我们来说太难了，因为点数太多
了，所以上帝删掉了这(N+1)×(M+1)中的K个点。既然点变少了，问题也就变简单了，那么这个时候这些格点组成
了多少个正方形呢？
Input
第一行三个整数 N, M, K， 代表棋盘的行数、 列数和不能选取的顶点个数。 保证 N, M >= 1， K <=(N + 1) ×
(M + 1)。约定每行的格点从上到下依次用整数 0 到 N 编号，每列的格点依次用 0到 M 编号。接下来 K 行，每
行两个整数 x,y 代表第 x 行第 y 列的格点被删掉了。保证 0 <=x <=N<=10^6, 0 <=y<=M<=10^6，K<=2*1000且不
会出现重复的格点。
Output
仅一行一个正整数， 代表正方形个数对 100000007（ 10^8 + 7） 取模之后的值
容斥，不考虑删点的方案数可以O(min(n,m))枚举正方形在水平方向投影的长度算出
恰好删去2~4点的方案数可以O(k2)枚举其中的两个点，再看正方形另外两点是否也被删去
还有过定点的正方形数，可以列出8条不等式，求半平面交，然后因为一些特殊的性质，用pick定理可以算出半平面交内整点数（似乎有比这简洁的多的方法）
然后加加减减就得到答案了
#include<cstdio>#include<algorithm>int s[107][107];int n,m,k;typedef long long i64;const int P=1e8+7;int min(int a,int b){return a<b?a:b;}int max(int a,int b){return a>b?a:b;}struct pos{int x,y;}ps[17];struct hp{int a,b,c;}hs[17],ls[17];pos operator&(hp u,hp v){ int r=u.a*v.b-u.b*v.a; if((u.c*v.b-u.b*v.c)%r||(u.a*v.c-u.c*v.a)%r)putchar(‘*‘); return (pos){(u.c*v.b-u.b*v.c)/r,(u.a*v.c-u.c*v.a)/r};}bool operator==(pos a,pos b){return a.x==b.x&&a.y==b.y;}i64 operator*(pos a,pos b){return i64(a.x)*b.y-i64(a.y)*b.x;}pos operator-(pos a,pos b){return (pos){a.x-b.x,a.y-b.y};}pos operator+(pos a,pos b){return (pos){a.x+b.x,a.y+b.y};}bool in(pos a,hp b){return a.x*b.a+a.y*b.b<=b.c;}bool chk(hp a,hp b,hp c){return !in(a&b,c);}int gcd(int a,int b){return b?gcd(b,a%b):a;}int abs(int x){return x>0?x:-x;}int count(pos w){return gcd(abs(w.x),abs(w.y));}i64 cal(int x,int y){ int L=-x,R=n-x,U=-y,D=m-y; int p=0; #define _(a,b,c) hs[p++]=(hp){a,b,c} _(0,1,min(D,-L)); _(1,1,D); _(1,0,min(R,D)); _(1,-1,R); _(0,-1,-max(U,-R)); _(-1,-1,-U); _(-1,0,-max(L,U)); _(-1,1,-L); hs[p]=hs[0]; int l=0,r=0; for(int i=0;i<p;++i){ while(r-l>=2&&chk(ls[r-2],ls[r-1],hs[i]))--r; while(r-l>=2&&chk(ls[l+1],ls[l],hs[i]))++l; ls[r++]=hs[i]; } while(r-l>=2&&chk(ls[r-2],ls[r-1],ls[l]))--r; ls[r]=ls[l]; for(int i=l;i<r;++i)ps[i]=ls[i+1]&ls[i]; r=std::unique(ps+l,ps+r)-ps-l; ps[r]=ps[l]; if(r-l==2)return count(ps[l+1]-ps[l]); i64 ans=0; for(int i=l;i<r;++i){ ans+=count(ps[i+1]-ps[i]); ans+=ps[i+1]*ps[i]; } return ans/2;}pos xs[2007],ht[12347];bool hd[12347];void ins(pos x){ int w=(x.x*293+x.y*149)%12347; while(hd[w])w=(w+3555)%12347; hd[w]=1;ht[w]=x;}bool operator<(pos a,pos b){return a.x!=b.x?a.x<b.x:a.y<b.y;}i64 d0,d1,d2,d3,d4;bool exist(pos x){ int w=(x.x*293+x.y*149)%12347; while(hd[w]){ if(ht[w]==x)return 1; w=(w+3555)%12347; } return 0;}bool in(pos a){return a.x>=0&&a.x<=n&&a.y>=0&&a.y<=m;}int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=0;i<k;++i)scanf("%d%d",&xs[i].x,&xs[i].y),ins(xs[i]); int s=min(n,m); for(int i=1;i<=s;++i)d0=(d0+i*i64(n+1-i)*(m+1-i))%P; for(int i=0;i<k;++i){ d1=(d1+cal(xs[i].x,xs[i].y))%P; for(int j=i+1;j<k;++j){ pos d=xs[j]-xs[i]; if(~d.x+d.y&1){ pos a=(pos){d.x+d.y>>1,-d.x+d.y>>1}; pos p1=xs[i]+a,p2=xs[j]-a; if(in(p1)&&in(p2)){ int e1=exist(p1); int e2=exist(p2); d4+=e1&e2; d3+=e1^e2; d2+=~(e1|e2)&1; } } d=(pos){d.y,-d.x}; pos p1=xs[i]+d,p2=xs[i]-d,p3=xs[j]+d,p4=xs[j]-d; if(in(p1)&&in(p3)){ int e1=exist(p1); int e3=exist(p3); d4+=(e1&e3); d3+=(e1^e3); d2+=(~(e1|e3)&1); } if(in(p2)&&in(p4)){ int e2=exist(p2); int e4=exist(p4); d4+=(e2&e4); d3+=(e2^e4); d2+=(~(e2|e4)&1); } } } d4/=6;d3/=3; d1-=d2+d3*2+d4*3; d0-=d1; printf("%lld",(d0+P)%P); return 0;}
bzoj4558: [JLoi2016]方
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。