3D点的查询

Question

3D点的查询

3

我有一个三维点的数组。每个点都有x、y和z坐标。数组的最大大小可以是777777。我有Q个查询，每个查询都提供四个数字A、B、C、D。对于每个查询，我必须输出以下总和。

Q <=77
1 <= A, B, C <=77
1 <= Xi, Yi, Zi <=77
1 <= Di <= 777
N <= 777777

我已经完成的工作：对于每个查询，使用两个嵌套循环计算给定的总和，导致复杂度为O(Q*N^2)。有没有更好的方法来计算它？

编辑：我确定的是这不是一个几何问题。xi-xj的最大值为76，最小值为-76。yi和zi也是如此。因此，总共可能的组合数为153*153*153。现在，在一个查询中，我们必须计算数组中特定组合出现的次数，并仅对该组合解决一次总和。问题转化为找到特定组合（xi-xj，yi-yj，zi-zj）出现的次数。有人能从这里开始吗？我怀疑我们可以在这里使用快速傅里叶变换。我以前见过它们用于这些类型的问题。但我不知道如何开始。

- lassaendie

如果你在这里得不到答案，可以尝试math.stackexchange.com。 - m69 ''snarky and unwelcoming''

确实存在四次方吗？如果它们是二次幂，那就有几何意义了。 - stgatilov

1

@stgatilov 是的，它们实际上是四次方。 - lassaendie

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mcdowella · Answer 1

以下是一个错误，因为它忽略了绝对值函数。我看不到任何解决方法。

您可以将查询重写为 A * SUM_i!=j (Xi-Xj)/sqrt(...) + B * SUM_i!=j(Yi-Yj)/sqrt(...) + ...

一旦您完成了这个步骤，您会发现如果您已经计算了A=1，B=C=D=0和B=1，A=C=D=0和C=1，A=B=D=0和D=1，A=B=C=0等的值，例如Qa，Qb，Qc，Qd，那么您可以找到任何其他A，B，C和D值的值，如A * Qa + B * Qb + C * Qc + D * Qd。

这将把复杂度降至O（N ^ 2）。