玲珑杯1143

1143 - 计算几何你瞎暴力

Time Limit：5s Memory Limit：256MByte

Submissions：1735Solved：341

DESCRIPTION

今天$HH$考完了期末考试,他在教学楼里闲逛,他看着教学楼里一间间的教室,于是开始思考:

如果从一个坐标为 $(x_1,y_1,z_1)$的教室走到$(x_2,y_2,z_2)$的距离为$|x_1-x_2|+|y_1-y_2|+|z_1-z_2|$

那么有多少对教室之间的距离是不超过$R$的呢?

INPUT

第一行是一个整数$T(1\le T\le 10)$, 表示有$T$组数据接下来是$T$组数据,对于每组数据:第一行是两个整数$n,q(1\le n\le 5\times {10}^4,1\le q\le {10}^3)$, 表示有$n$间教室,$q$次询问.接下来是$n$行, 每行3个整数$x_i,y_i,z_i(0\le x_i,y_i,z_i\le 10)$,表示这间教室的坐标.最后是$q$行,每行一个整数$R(0\le R\le {10}^9)$,意思见描述.

OUTPUT

对于每个询问$R$输出一行一个整数,表示有多少对教室满足题目所述的距离关系.

SAMPLE INPUT

13 30 0 01 1 11 1 1123

SAMPLE OUTPUT

113

HINT

对于样例,1号教室和2号教室之间的距离为3, 1号和3号之间的距离为3, 2号和3号之间的距离为0

#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include<functional>
using  namespace std;
typedef long long ll;
#define pd(x) printf("%d
",x)
const double eps=1e-6;
const double PI=acos(-1.0);
const int INF=1e9+10;
const int MOD=1e9+7;
const int N=1e6+10;
int w[20][20][20];
ll dis[10000];
//char s[N];
struct Node
{
    int x,y,z;
} node[N];
int main()
{
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i<=10; i++)
            for(int j=0; j<=10; j++)
                for(int k=0; k<=10; k++)
                    w[i][j][k]=0;
        memset(dis,0,sizeof(dis));
        int x,y,z,r,k=0;//总共有k个不同的点
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            if(!w[x][y][z])
            {
                node[k].x=x,node[k].y=y;
                node[k].z=z;
                k++;
            }
            w[x][y][z]++;//每个点出现的次数
        }
//        printf("%d
",k);
        for(int i=0; i<k; i++)
        {
            int x1=node[i].x,y1=node[i].y,z1=node[i].z;
            int num1=w[x1][y1][z1];
            for(int j=i+1; j<k; j++)
            {
                int x2=node[j].x,y2=node[j].y,z2=node[j].z;
                int num2=w[x2][y2][z2];
                int diss=abs(x1-x2)+abs(y1-y2)+abs(z1-z2);
                dis[diss]+=num2*num1;
            }
        }
        while(m--)
        {
            scanf("%d",&r);
            r=min(r,30);
            ll ans=0;
            for(int i=0; i<k; i++)
            {
                x=node[i].x,y=node[i].y,z=node[i].z;
                ll num=w[x][y][z];
                ans+=(num-1)*num/2;
            }
            for(int i=1; i<=r; i++) ans+=dis[i];
            printf("%lld
",ans);
        }
    }
    return 0;
}
我会说这是别人的代码？