// setter's code #pragma comment(linker, "/STACK:100000000") #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std; typedef complex < double > cd; const double pi = acos(-1.0); const int MaxN = 777777; const int MaxH = 77; const int MaxLen = 1 << 22; const int MaxQ = 77; int n, w, h, t, q; int mt[MaxH + 1][MaxH + 1][MaxH + 1]; cd A[MaxLen], B[MaxLen], W[MaxLen]; cd D[MaxLen]; int a[MaxLen], b[MaxLen]; int x[MaxN + 1], y[MaxN + 1], z[MaxN + 1]; double res[MaxQ + 1]; int qa[MaxQ + 1], qb[MaxQ + 1], qc[MaxQ + 1], qd[MaxQ + 1]; template < class P, class Q > void fft(P *p, Q *y, int n, int k = 1) { if(n > 1) { fft(p, y, n >>= 1, k << 1); fft(p + k, y + n, n, k << 1); for(int i = 0, j = 0; i < n; ++i, j += k) { Q r = W[j] * y[i + n]; y[i + n] = y[i] - r; y[i] += r; } } else { *y = *p; } } void read() { scanf("%d%d", &n, &q); for(int i = 1; i <= n; ++i) { scanf("%d%d%d", &x[i], &y[i], &z[i]); } for(int i = 1; i <= q; ++i) { scanf("%d%d%d%d", &qa[i], &qb[i], &qc[i], &qd[i]); } } double naive(double A, double B, double C, double D) { double ans = 0; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { if(i == j) continue; int dx = x[j] - x[i], dy = y[j] - y[i], dz = z[j] - z[i]; ans += abs(A * dx + B * dy + C * dz + D) / sqrt(.0 + dx * dx * dx * dx + dy * dy * dy * dy + dz * dz * dz * dz); } } return ans; } void solve() { w = h = t = 0; for(int i = 1; i <= n; ++i) { mt[x[i] - 1][y[i] - 1][z[i] - 1] += 1; w = max(w, x[i]); h = max(h, y[i]); t = max(t, z[i]); } for(int i = 0; i < w; ++i) { for(int j = 0; j < h; ++j) { for(int k = 0; k < t; ++k) { a[(0 + i) * 4 * h * t + (0 + j) * 2 * t + (0 + k)] += mt[i][j][k]; b[(w - i) * 4 * h * t + (h - j) * 2 * t + (t - k)] += mt[i][j][k]; } } } int len = 1; while(len < 8 * w * h * t) { len += len; } for(int i = 0; i < len; ++i) { A[i] = cd(a[i], b[i]); W[i] = polar(1.0, 2 * pi * i / len); } fft(A, D, len); for(int i = 0; i < len; ++i) { int le = i, ri = (len - i) % len; A[i] = cd((D[le].real() + D[ri].real()) / 2.0, (D[le].imag() - D[ri].imag()) / 2.0); B[i] = cd((D[le].imag() + D[ri].imag()) / 2.0, (D[ri].real() - D[le].real()) / 2.0); A[i] *= B[i]; W[i] = conj(W[i]); } fft(A, B, len); for(int i = 0; i < len; ++i) { long long cnt = (long long)(B[i].real() / len + 0.5); if(!cnt) continue; int dx = i / (4 * h * t) - w; int dy = i % (4 * h * t) / (2 * t) - h; int dz = i % (2 * t) - t; if(dx == 0 && dy == 0 && dz == 0) { continue; } double Len = sqrt(0.0 + dx * dx * dx * dx + dy * dy * dy * dy + dz * dz * dz * dz); for(int k = 1; k <= q; ++k) { double Val = abs(qa[k] * dx + qb[k] * dy + qc[k] * dz + qd[k]); res[k] += 1.0 * cnt * Val / Len; } } } int main() { read(); solve(); cout.precision(15); for(int i = 1; i <= q; ++i) { cout << fixed << res[i] / n / (n - 1) << endl; } return 0; }