bzoj1173: [Balkan2007]Point

时间:2021-02-02 20:28:26

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!=?x<:y!=?y<:z<)x=-x,y=-y,z=-z;
}
}ps[];
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[*];
bool operator<(const line&a,const line&b){return a.v<b.v;}
int ap=,ans=;
int es[],enx[],e0[],ep=,ds[],dp=,T,tk[];
int dfs(int w){
int c=;
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=;i<=n;++i)scanf("%d%d%d",&ps[i].x,&ps[i].y,&ps[i].z);
for(int i=;i<=n;++i){
for(int j=;j<i;++j){
(as[ap++]=(line){i,j,ps[i]-ps[j]}).v.fix();
}
}
std::sort(as,as+ap);
for(int i=,j=;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=;k<dp;++k)if(dfs(ds[k])>=)++ans;
while(dp)e0[ds[--dp]]=;ep=;
}
printf("%d\n",ans);
return ;
}