如果原点能被一个光源照到,那么这两个点之间一定没有任何球。我们可以通过三分距离来确定某线段和球是否有交点。

注意到m非常小,于是我们可以枚举原点被哪些光源照到。由于\(O(3^{m}*n)\)会超时,我们可以对每个光源需要移走那些球进行压位。

复杂度\(O(3^{m}*n / w)\)

跑的有点慢啊……

#include <bits/stdc++.h>
#define UI unsigned int
#define N 2100
#define eps 0.000001
using namespace std;
int n, m, r;
struct node
{
double x, y, z;
} light[N], tar;
struct circle
{
node O; double r;
} ball[N];
double power[N];
void get(int t, int &d, int &u)
{
u = t >> ;
d = t ^ (u << );
}
double dist(node A, node B)
{
return pow(pow(A.x - B.x, ) + pow(A.y - B.y, ) + pow(A.z - B.z, ), 0.5);
}
node get(node A, node B, double d)
{
node nw;
nw.x = (B.x - A.x) * d + A.x;
nw.y = (B.y - A.y) * d + A.y;
nw.z = (B.z - A.z) * d + A.z;
return nw;
}
UI shel[][];
UI nowi[][];
int st[];
int ok[];
double ans;
int main()
{
for (int i = ; i < ( << ); ++ i)
for (int j = ; j < ; ++ j)
if (i & ( << j))
st[i] ++; while (scanf("%d%d%d", &n, &m, &r), n + m + r)
{
ans = ;
for (int i = ; i < n; ++ i)
scanf("%lf%lf%lf%lf", &ball[i].O.x, &ball[i].O.y, &ball[i].O.z, &ball[i].r);
for (int i = ; i < m; ++ i)
scanf("%lf%lf%lf%lf", &light[i].x, &light[i].y, &light[i].z, &power[i]);
scanf("%lf%lf%lf", &tar.x, &tar.y, &tar.z);
for (int i = ; i < m; ++ i) power[i] /= pow(dist(tar, light[i]), );
for (int i = ; i < m; ++ i)
for (int j = ; j < n / + ; ++ j)
shel[i][j] = ;
for (int i = ; i < m; ++ i)
for (int j = ; j < n; ++ j)
{
if (dist(ball[j].O, tar) < ball[j].r && dist(ball[j].O, light[i]) < ball[j].r) continue;
int d, u;
get(j, d, u);
double l = , r = ;
while (r - l > eps)
{
double m1 = (l + l + r) / , m2 = (l + r + r) / ;
node p1 = get(tar, light[i], m1), p2 = get(tar, light[i], m2);
if (dist(ball[j].O, p1) < dist(ball[j].O, p2))
{
if (dist(ball[j].O, p1) < ball[j].r) shel[i][u] |= << d;
r = m2;
}
else
{
if (dist(ball[j].O, p2) < ball[j].r) shel[i][u] |= << d;
l = m1;
}
}
}
for (int i = ; i < ( << m); ++ i)
{
ok[i] = ;
for (int j = ; ( << j) < i; j ++)
if (i & ( << j))
if (!ok[i ^ ( << j)]) ok[i] = ;
if (!ok[i]) continue;
for (int j = ; ( << j) <= i; j ++)
if (i & ( << j))
{
int s = ;
for (int k = ; k < n / + ; ++ k)
{
nowi[i][k] = nowi[i ^ ( << j)][k] | shel[j][k];
s += st[nowi[i][k] >> ] + st[nowi[i][k] ^ ((nowi[i][k] >> ) << )];
}
ok[i] = (s <= r);
break;
}
if (ok[i])
{
double nowans = ;
for (int j = ; j < m; ++ j)
if (i & ( << j)) nowans += power[j];
ans = max(ans, nowans);
}
}
printf("%.6lf\n", ans);
}
}
05-11 17:05