首页 > 代码库 > bzoj1173: [Balkan2007]Point

bzoj1173: [Balkan2007]Point

Description

给出N个三维空间上的点. 问有多少条直线,这些直线上至少有三个点.

Input

第一行给出数字N,N在[4,1000] 下面N行,每行三个数字,用于描述点的坐标,其值在[-10000,10000]

Output

有多少条直线

枚举直线的方向,对每个方向建一个图,若两点间连线在这个方向上则连边,每个至少有三个点的联通块代表一条直线

#include<cstdio>#include<algorithm>inline int gcd(int x,int y){    for(int z;y;z=x,x=y,y=z%y);    return x;}int n;struct pos{    int x,y,z;    void fix(){        int g=gcd(gcd(x,y),z);        x/=g;y/=g;z/=g;        if(x!=0?x<0:y!=0?y<0:z<0)x=-x,y=-y,z=-z;    }}ps[1007];bool operator==(const pos&a,const pos&b){return a.x==b.x&&a.y==b.y&&a.z==b.z;}bool operator<(const pos&a,const pos&b){return a.x!=b.x?a.x<b.x:a.y!=b.y?a.y<b.y:a.z<b.z;}pos operator-(pos a,pos b){return (pos){a.x-b.x,a.y-b.y,a.z-b.z};}struct line{    int a,b;    pos v;}as[1007*555];bool operator<(const line&a,const line&b){return a.v<b.v;}int ap=0,ans=0;int es[1000007],enx[1000007],e0[1007],ep=2,ds[1007],dp=0,T,tk[1007];int dfs(int w){    int c=1;    tk[w]=T;    for(int i=e0[w];i;i=enx[i]){        int u=es[i];        if(tk[u]!=T)c+=dfs(u);    }    return c;}void adde(int a,int b){    if(!e0[a])ds[dp++]=a;    if(!e0[b])ds[dp++]=b;    es[ep]=b;enx[ep]=e0[a];e0[a]=ep++;    es[ep]=a;enx[ep]=e0[b];e0[b]=ep++;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;++i)scanf("%d%d%d",&ps[i].x,&ps[i].y,&ps[i].z);    for(int i=1;i<=n;++i){        for(int j=1;j<i;++j){            (as[ap++]=(line){i,j,ps[i]-ps[j]}).v.fix();        }    }    std::sort(as,as+ap);    for(int i=0,j=0;i<ap;){        for(;j<ap&&as[i].v==as[j].v;++j);        for(++T;i<j;++i)adde(as[i].a,as[i].b);        for(int k=0;k<dp;++k)if(dfs(ds[k])>=3)++ans;        while(dp)e0[ds[--dp]]=0;ep=2;    }    printf("%d\n",ans);    return 0;}

 

bzoj1173: [Balkan2007]Point