2012-A3-0005

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

此题求：一个n×m的格点矩形中，三角形数量。

任意三点为一个三角形或共线，于是只要 C^3^,,(n+1)*(m+1),, - 三点共线数量即可

此题可以枚举子矩形来计算三点共共线的数量，比较好写。

我采用的是枚举斜率的方法，很容易写错

水平的垂直的计算较为简单，

然后x,y分别从1..m, 1..n，枚举只有gcd(x,y)==1才是有效斜率。

枚举完斜率再枚举斜率步长，就可以知道此斜率下线段的格点数，计算选3的组合即可。

注意：这样会使不同步长的点重复计算，可以设置一个比他小步长的矩形来规避，这样就转化为，一个矩形，中挖去一个矩形，再与两个半平面分别求交，然后求并的计算，挣扎了好久终于实现了。

这个和枚举矩形的时间复杂度是一样的,只是比较难写..


{{{
#include<cstdio>
#include<algorithm>
using namespace std;
typedef unsigned long long num;

num C3[1024];
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
int main(){
    for(int i=0;i<1024;++i)C3[i]=i*(i-1)*(i-2)/6;
    int mx,my,mm,xx,px,py,n,m,dx,dy,pp,x,y,z;
    //num tt;
    for(num tot;scanf("%d%d",&n,&m)==2;printf("%llu\n",tot)){


        tot =(n+1)*(m+1);
        tot = tot*(tot-1)*(tot-2)/6;
        tot -= C3[n+1]*(m+1);
        tot -= C3[m+1]*(n+1);

        for(x=1;x<=m;++x)
        for(y=1;y<=n;++y)if(gcd(x,y)==1){
            z = min(m/x,n/y);
            if(z<2)continue;
            px = m -x * z;
            py = n -y * z;
            tot -= (px+1)*(py+1)*2*C3[z+1];
            for(--z;z>1;--z){
                mx = m-x*z;
                my = n-y*z;
                pp = (mx+1)*(my+1)-(px+1)*(py+1);
                if(mx>=x && my>=y){
                    pp -= (mx-x+1)*(my-y+1);
                    if(px>=x && py >= y){
                        pp+= (py-y+1)*(px-x+1);
                    }
                }
                tot -= (pp<<1)*C3[z+1];
                px = mx;
                py = my;

            }
        }
    }
}
}}}

此题求：一个n×m的格点矩形中，三角形数量。

任意三点为一个三角形或共线，于是只要 C³_(n+1)*(m+1) - 三点共线数量即可

此题可以枚举子矩形来计算三点共共线的数量，比较好写。

我采用的是枚举斜率的方法，很容易写错

水平的垂直的计算较为简单，

然后x,y分别从1..m, 1..n，枚举只有gcd(x,y)==1才是有效斜率。

枚举完斜率再枚举斜率步长，就可以知道此斜率下线段的格点数，计算选3的组合即可。

注意：这样会使不同步长的点重复计算，可以设置一个比他小步长的矩形来规避，这样就转化为，一个矩形，中挖去一个矩形，再与两个半平面分别求交，然后求并的计算，挣扎了好久终于实现了。

这个和枚举矩形的时间复杂度是一样的,只是比较难写..

#include<cstdio>
#include<algorithm>
using namespace std;
typedef unsigned long long num;
num C3[1024];
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
int main(){
    for(int i=0;i<1024;++i)C3[i]=i*(i-1)*(i-2)/6;
    int mx,my,mm,xx,px,py,n,m,dx,dy,pp,x,y,z;
    //num tt;
    for(num tot;scanf("%d%d",&n,&m)==2;printf("%llu\n",tot)){
        tot =(n+1)*(m+1);
        tot = tot*(tot-1)*(tot-2)/6;
        tot -= C3[n+1]*(m+1);
        tot -= C3[m+1]*(n+1);
        for(x=1;x<=m;++x)
        for(y=1;y<=n;++y)if(gcd(x,y)==1){
            z = min(m/x,n/y);
            if(z<2)continue;
            px = m -x * z;
            py = n -y * z;
            tot -= (px+1)*(py+1)*2*C3[z+1];
            for(--z;z>1;--z){
                mx = m-x*z;
                my = n-y*z;
                pp = (mx+1)*(my+1)-(px+1)*(py+1);
                if(mx>=x && my>=y){
                    pp -= (mx-x+1)*(my-y+1);
                    if(px>=x && py >= y){
                        pp+= (py-y+1)*(px-x+1);
                    }
                }
                tot -= (pp<<1)*C3[z+1];
                px = mx;
                py = my;
            }
        }
    }
}