首页 > 代码库 > “玲珑杯”ACM比赛 Round #18 A 计算几何你瞎暴力（瞎暴力）
“玲珑杯”ACM比赛 Round #18 A 计算几何你瞎暴力（瞎暴力）
题目链接：http://www.ifrog.cc/acm/problem/1143
题意：如果从一个坐标为 (x1,y1,z1)(x1,y1,z1)的教室走到(x2,y2,z2)(x2,y2,z2)的距离为 |x1−x2|+|y1−y2|+|z1−z2|
那么有多少对教室之间的距离是不超过R的呢?
题解：暴力暴力，把点记录在三维数组里面，然后暴力搜寻符合条件的点，值得注意的是在同个位置可能有不同的教室（明显不符合现实，蜜汁尴尬（逃.....）
不同位置直接暴力，会重复计算一次，比如点（1，2，3）和点（4，5，6）反过来会多计算一次，把相同位置的教室计算值也扩大一倍，最后一起除以2。
数据有点大，用int会爆，要用long long 。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 typedef long long LL; 7 LL map[11][11][11]; 8 LL ans[33]; 9 10 int main(){11 LL t; 12 cin>>t;13 while(t--){14 memset(map,0,sizeof(map));15 memset(ans,0,sizeof(ans));16 17 LL x,y,z,n,q,R;18 cin>>n>>q;19 20 for(int i=1;i<=n;i++){21 cin>>x>>y>>z;22 map[x][y][z]++;23 }24 25 26 for(int i=0;i<=10;i++)27 for(int j=0;j<=10;j++)28 for(int k=0;k<=10;k++)29 for(int a=0;a<=10;a++)30 for(int b=0;b<=10;b++)31 for(int c=0;c<=10;c++){32 if(map[i][j][k]&&map[a][b][c]){33 if(i==a&&j==b&&k==c){34 LL t1=map[i][j][k];35 ans[0]+=(t1-1)*t1;36 }37 else{38 LL t2=abs(i-a)+abs(j-b)+abs(k-c);39 ans[t2]+=map[i][j][k]*map[a][b][c];40 }41 }42 }43 44 for(int i=0;i<=30;i++) ans[i]/=2;45 for(int i=1;i<=30;i++) ans[i]+=ans[i-1];46 47 for(int i=1;i<=q;i++){48 cin>>R;49 if(R>30) R=30;50 cout<<ans[R]<<endl;51 }52 53 }54 return 0;55 }
“玲珑杯”ACM比赛 Round #18 A 计算几何你瞎暴力（瞎暴力）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。