ACM学习历程—FZU 2144 Shooting Game（计算几何 && 贪心 && 排序）

Description

Fat brother and Maze are playing a kind of special (hentai) game in the playground. (Maybe it’s the OOXX game which decrypted in the last problem, who knows.) But as they don’t like using repellent while playing this kind of special (hentai) game, they really suffer a lot from the mosquito. So they decide to use antiaircraft gun to shoot the mosquito. You can assume that the playground is a kind of three-dimensional space and there are N mosquitoes in the playground. Each of them is a kind of point in the space which is doing the uniform linear motion. (匀速直线运动) Fat brother is standing at (0, 0, 0) and once he shoot, the mosquito who’s distance from Fat brother is no large than R will be shot down. You can assume that the area which Fat brother shoot is a kind of a sphere with radio R and the mosquito inside this sphere will be shot down. As Fat brother hate these mosquito very much, he wants to shoot as much mosquito as he can. But as we all know, it’s tired for a man to shoot even if he is really enjoying this. So in addition to that, Fat brother wants to shoot as less time as he can.

You can (have to) assume that Fat brother is strong enough and he don’t need to rest after shooting which means that can shoot at ANY TIME.

Input

The first line of the date is an integer T, which is the number of the text cases.

Then T cases follow, each case starts with two integers N and R which describe above.

Then N lines follow, the ith line contains six integers ax, ay, az, dx, dy, dz. It means that at time 0, the ith mosquito is at (ax, ay, az) and it’s moving direction is (dx, dy, dz) which means that after time t this mosquito will be at (ax+dx*t, ay+dy*t, ax+dz*t). You can assume that dx*dx + dy*dy+ dz*dz > 0.

1 <= T <= 50, 1 <= N <= 100000, 1 <= R <= 1000000

-1000000 <= ax, ay, az <= 1000000

-100 <= dx, dy, dz <= 100

The range of each coordinate is [-10086, 10086]

Output

For each case, output the case number first, then output two numbers A and B.

A is the number of mosquito Fat brother can shoot down.

B is the number of times Fat brother need to shoot.

Sample Input

6

2 1

2 0 0 -1 0 0

-2 0 0 1 0 0

2 1

4 0 0 -1 0 0

-2 0 0 1 0 0

2 1

4 0 0 -1 0 0

1 0 0 1 0 0

2 1

1 1 1 1 1 1

-1 -1 -1 -1 -1 -1

1 1

0 0 0 1 0 0

3 1

-1 0 0 1 0 0

-2 0 0 1 0 0

4 0 0 -1 0 0

Sample Output

Case 1: 2 1

Case 2: 2 1

Case 3: 2 2

Case 4: 0 0

Case 5: 1 1

Case 6: 3 2

题目大意是求在射程内能射死几个mosquito，而且要求射击次数最少，因为一次射击能射死射程内所有mosquito。

一开始反应是先求出mosquito运动直线与射击者的最近距离，虽然最后算出了最近坐标和距离，发现多次一举。

其实直接设能射击的时刻是t。

那么

其中a、b、c是加速度矢量的三个分量。

然后取临界等号，就能算出进入射击范围的时间from和出射击范围的时间to。

先判断方程是否有解。

然后再判断from和to的正负性。

于是就能得到一系列的mosquito的时间序列。（需要注意的是from小于0的需要设置为0）

最后就是优先按照to时间进行排序，其次按照from排序。

然后进行一次贪心，对于当前标记点的to，所有后面的from小于等于当前点to的点都可以与当前点在同一时间射击。因为保证了后面的点的to时间比当前时间的to时间大。

PS：如果按照double型直接输入会报超时。。。。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>

using namespace std;

inline double pow2(double x)
{
    return x*x;
}

struct node
{
    double from, to;
}t[100005];

bool cmp(node a, node b)
{
    if (a.to != b.to)
        return a.to < b.to;
    else
        return a.from < b.from;
}

int n, r, cnt, ans;
int px, py, pz;

void Work()
{
    scanf("%d%d", &n, &r);
    int a, b, c;
    double A, B, C, t1, t2, deta;
    cnt = 0;
    ans = 0;
    for (int i = 0; i < n; ++i)
    {
        scanf("%d%d%d", &px, &py, &pz);
        scanf("%d%d%d", &a, &b, &c);
        A = pow2(a) + pow2(b) + pow2(c);
        B = 2*(a*px + b*py + c*pz);
        C = pow2(px) + pow2(py) + pow2(pz) - pow2(r);
        deta = pow2(B) - 4*A*C;
        if (deta >= 0)
        {
            t1 = (-B-sqrt(deta))/A/2;
            t2 = (-B+sqrt(deta))/A/2;
            if (t1 < 0)
                t1 = 0;
        }

        if (deta >= 0 && t2 >= 0)
        {
            t[cnt].from = t1;
            t[cnt].to = t2;
            cnt++;
        }
    }
    printf("%d ", cnt);

    sort(t, t+cnt, cmp);
    int i, j;
    for (i = 0; i < cnt;)
    {
        j = i+1;
        while (t[j].from <= t[i].to && j < cnt)
        {
            j++;
        }
        ans++;
        i = j;
    }
    printf("%d\n", ans);
}

int main()
{
    //freopen("test.in", "r", stdin);
    int T;
    scanf("%d", &T);
    for (int times = 1; times <= T; ++times)
    {
        printf("Case %d: ", times);
        Work();
    }
    return 0;
}