bzoj4691: Let There Be Light

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

注意到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);

    }

}