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(k²)枚举其中的两个点，再看正方形另外两点是否也被删去

还有过定点的正方形数，可以列出8条不等式，求半平面交，然后因为一些特殊的性质，用pick定理可以算出半平面交内整点数（似乎有比这简洁的多的方法）

然后加加减减就得到答案了

#include<cstdio>

#include<algorithm>

int s[][];

int n,m,k;

typedef long long i64;

const int P=1e8+;

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[];

struct hp{int a,b,c;}hs[],ls[];

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>?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=;

    #define _(a,b,c) hs[p++]=(hp){a,b,c}

    _(,,min(D,-L));

    _(,,D);

    _(,,min(R,D));

    _(,-,R);

    _(,-,-max(U,-R));

    _(-,-,-U);

    _(-,,-max(L,U));

    _(-,,-L);

    hs[p]=hs[];

    int l=,r=;

    for(int i=;i<p;++i){

        while(r-l>=&&chk(ls[r-],ls[r-],hs[i]))--r;

        while(r-l>=&&chk(ls[l+],ls[l],hs[i]))++l;

        ls[r++]=hs[i];

    }

    while(r-l>=&&chk(ls[r-],ls[r-],ls[l]))--r;

    ls[r]=ls[l];

    for(int i=l;i<r;++i)ps[i]=ls[i+]&ls[i];

    r=std::unique(ps+l,ps+r)-ps-l;

    ps[r]=ps[l];

    if(r-l==)return count(ps[l+]-ps[l]);

    i64 ans=;

    for(int i=l;i<r;++i){

        ans+=count(ps[i+]-ps[i]);

        ans+=ps[i+]*ps[i];

    }

    return ans/;

}

pos xs[],ht[];

bool hd[];

void ins(pos x){

    int w=(x.x*+x.y*)%;

    while(hd[w])w=(w+)%;

    hd[w]=;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*+x.y*)%;

    while(hd[w]){

        if(ht[w]==x)return ;

        w=(w+)%;

    }

    return ;

}

bool in(pos a){return a.x>=&&a.x<=n&&a.y>=&&a.y<=m;}

int main(){

    scanf("%d%d%d",&n,&m,&k);

    for(int i=;i<k;++i)scanf("%d%d",&xs[i].x,&xs[i].y),ins(xs[i]);

    int s=min(n,m);

    for(int i=;i<=s;++i)d0=(d0+i*i64(n+-i)*(m+-i))%P;

    for(int i=;i<k;++i){

        d1=(d1+cal(xs[i].x,xs[i].y))%P;

        for(int j=i+;j<k;++j){

            pos d=xs[j]-xs[i];

            if(~d.x+d.y&){

                pos a=(pos){d.x+d.y>>,-d.x+d.y>>};

                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)&;

                }

            }

            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)&);

            }

            if(in(p2)&&in(p4)){

                int e2=exist(p2);

                int e4=exist(p4);

                d4+=(e2&e4);

                d3+=(e2^e4);

                d2+=(~(e2|e4)&);

            }

        }

    }

    d4/=;d3/=;

    d1-=d2+d3*+d4*;

    d0-=d1;

    printf("%lld",(d0+P)%P);

    return ;

}

巴特西

bzoj4558: [JLoi2016]方

Description

Input

Output

最新文章

热门文章