首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。