UVALive 6188 (LA 6188) Let There Be Light 计算几何

题目大意：

就是现在给M = 15个光源, 然后每个光源(Tx, Ty, Tz)和Td, 对于一个点(Ex, Ey, Ez)处能产生的贡献根据公式给出了

然后空间中有N = 2000个球, 现在可以从中删除R个球使得目标点出的贡献最大

一个点光源能够造成贡献是没有球能挡住这个点光源到目标点的光线

球是空心的

大致思路：

首先可以处理出每个点光源如果要对目标点产生贡献需要删去哪些球(也就是线段和球面有交点的球)

然后2^15暴力枚举有哪些光源产生影响, 计算这个情况下需要删去多少球, 当这个数量小于R的时候就更新答案

代码如下：

Result  :  Accepted     Memory  :  ? KB     Time  :  866 ms

/*
 * Author: Gatevin
 * Created Time:  2015/11/7 14:45:05
 * File Name: Sakura_Chiyo.cpp
 */
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;

int N, M, r;

struct Point
{
    double x, y, z;
    Point(){}
    Point(double _x, double _y, double _z)
    {
        x = _x, y = _y, z = _z;
    }
};

//Point p[15];
double R[2010];
Point cen[2010];
Point target;
Point light[20];
double T[20];

double sqr(double d)
{
    return d*d;
}

double nani(Point p1, int id)
{
    return T[id]/(sqr(light[id].x - p1.x) + sqr(light[id].y - p1.y) + sqr(light[id].z - p1.z));
}

double dis(Point p1, Point p2)
{
    return sqrt(sqr(p1.x - p2.x) + sqr(p1.y - p2.y) + sqr(p1.z - p2.z));
}

bitset<2010> mabi[20];

bool in(Point p, int ball_id)
{
    if(dis(p, cen[ball_id]) < R[ball_id]) return true;
    return false;
}

Point operator-(Point p1, Point p2)
{
    return Point(p1.x - p2.x, p1.y - p2.y, p1.z - p2.z);
}

double dot(Point p1, Point p2)
{
    return p1.x*p2.x + p1.y*p2.y + p1.z*p2.z;
}

bool check(int light_id, int ball_id)
{
    if(in(light[light_id], ball_id) && in(target, ball_id)) return false;
    if(in(light[light_id], ball_id) || in(target, ball_id)) return true;
    double a = dis(light[light_id], target);
    double b = dis(light[light_id], cen[ball_id]);
    double c = dis(cen[ball_id], target);
    double p = (a + b + c) / 2.;
    double S = sqrt(p*(p - a)*(p - b)*(p - c));
    double d = 2*S/a;
    if(d < R[ball_id] && 
            (dot(light[light_id] - target, light[light_id] - cen[ball_id]) > 0 && 
             dot(target - cen[ball_id], target - light[light_id]) > 0 )) return true;
    return false;
}

int main()
{
    while(scanf("%d %d %d", &N, &M, &r), N || M || r)
    {
        for(int i = 0; i < N; i++)
            scanf("%lf %lf %lf %lf", &cen[i].x, &cen[i].y, &cen[i].z, &R[i]);
        for(int i = 0; i < M; i++)
            scanf("%lf %lf %lf %lf", &light[i].x, &light[i].y, &light[i].z, &T[i]);
        scanf("%lf %lf %lf", &target.x, &target.y, &target.z);
        for(int i = 0; i < M; i++)
        {
            mabi[i].reset();
            for(int j = 0; j < N; j++)
                if(check(i, j))
                    mabi[i][j] = 1;
        }
        double ans = 0;
        for(int i = 0; i < (1 << M); i++)
        {
            bitset<2010> now;
            now.reset();
            double all = 0;
            for(int j = 0; j < M; j++)
                if(i & (1 << j))
                {
                    now |= mabi[j];
                    all += nani(target, j);
                }
            if(now.count() <= r)
                ans = max(ans, all);
        }
        printf("%.5f\n", ans);
    }
    return 0;
}

/*
12 5 4
0 10 0 1
1 5 0 2
1 4 0 2
0 0 0 2
10 0 0 1
3 -1 0 2
5 -1 0 2
10 10 0 15
0 -10 0 1
10 -10 0 1
-10 -10 0 1
10 10 0 1

0 10 0 240
10 0 0 200
10 -2 0 52
-10 0 0 100
1 1 0 2

0 0 0


12 5 4
0 10 0 1
1 5 0 2
1 4 0 2
0 0 0 2
10 0 0 1
3 -1 0 2
5 -1 0 2
10 10 0 15
0 -10 0 1
10 -10 0 1
-10 -10 0 1
10 10 0 1
0 10 0 260
10 0 0 200
10 -2 0 52
-10 0 0 100
1 1 0 2
0 0 0

5 1 3
1 2 0 2
-1 8 -1 8
-2 -3 5 6
-2 1 3 3
-4 2 3 5
1 1 2 7
0 0 0

5 1 2
1 2 0 2
-1 8 -1 8
-2 -3 5 6
-2 1 3 3
-4 2 3 5
1 1 2 7
0 0 0

0 0 0

*/