1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
| #include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <cmath>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
#define EPS 1e-8
#define equals(a,b) fabs((a) - (b)) < EPS
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
struct Point3D {
double x, y, z;
Point3D() : x(0), y(0), z(0) {}
Point3D(double x, double y, double z) : x(x), y(y), z(z) {}
Point3D operator+(const Point3D &o) const { return Point3D(x+o.x, y+o.y, z+o.z); }
Point3D operator-(const Point3D &o) const { return Point3D(x-o.x, y-o.y, z-o.z); }
Point3D operator*(const double m) const { return Point3D(x*m, y*m, z*m); }
Point3D operator/(const double d) const { return Point3D(x/d, y/d, z/d); }
bool operator==(const Point3D &o) const { return fabs(x-o.x) < EPS && fabs(y-o.y) < EPS; }
};
ostream& operator << (ostream& os, const Point3D& p) {
os << "(" << p.x << ", " << p.y << ", " << p.z << ")";
return os;
}
double dot(Point3D a, Point3D b) { return a.x * b.x + a.y * b.y + a.z * b.z; }
Point3D cross(Point3D a, Point3D b) { return Point3D(a.y*b.z - a.z*b.y, a.z*b.x - a.x*b.z, a.x*b.y - a.y*b.x); }
double norm(Point3D p) { return dot(p, p); }
double abs(Point3D p) { return sqrt(norm(p)); }
struct Line {
Point3D a, b;
Line() : a(Point3D(0, 0, 0)), b(Point3D(0, 0, 0)) {}
Line(Point3D a, Point3D b) : a(a), b(b) {}
};
ostream& operator << (ostream& os, const Line& l) {
os << "(" << l.a.x << ", " << l.a.y << ", " << l.a.z << ")-(" << l.b.x << "," << l.b.y << ", " << l.b.z << ")";
return os;
}
Point3D project(Line l, Point3D p) {
Point3D base = l.b - l.a;
double t = dot(base, p-l.a) / dot(base, base);
return l.a + base * t;
}
struct Ball {
Point3D p;
double r;
Ball() : p(Point3D(0, 0, 0)), r(0.0) {}
Ball(Point3D p, double r) : p(p), r(r) {}
};
ostream& operator << (ostream& os, const Ball& b) {
os << "(" << b.p.z << ", " << b.p.y << ", " << b.p.z << " :" << b.r << ")";
return os;
}
int main() {
int n, q;
cin >> n >> q;
vector<Ball> v(n);
vector<ll> cost(n);
rep(i, n) {
cin >> v[i].p.x >> v[i].p.y >> v[i].p.z >> v[i].r >> cost[i];
}
rep(i, q) {
ll ans = 0;
Point3D s, t;
cin >> s.x >> s.y >> s.z >> t.x >> t.y >> t.z;
Line line(s, t);
rep(j, n) {
Point3D proj = project(line, v[j].p);
if(abs(line.b - line.a) >= abs(proj - line.a) && abs(line.a - line.b) >= abs(proj - line.b)) {
if(abs(proj - v[j].p) < v[j].r + EPS) {
ans += cost[j];
}
}
}
cout << ans << endl;
}
return 0;
}
|