# FZU 2144 Shooting Game （贪心区域划分）

Problem 2144 Shooting Game Accept: 370 Submit: 1902 Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem 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

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;
#define MAX 100000
int t;
int n,r;
struct Node
{
double leftime;
double getime;
}a[MAX+5];
int cmp(Node a,Node b)
{
if(a.leftime==b.leftime)
return a.getime<b.getime;
return a.leftime<b.leftime;
}
int ans;
int res;
int tag[MAX+5];
int  main()
{
int x1,y1,z1,x2,y2,z2;
scanf("%d",&t);
int cas=0;
while(t--)
{
ans=0;
res=0;
scanf("%d%d",&n,&r);
int cnt=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
double a1=(x2*1.0)*(x2*1.0)+(y2*1.0)*(y2*1.0)+(z2*1.0)*(z2*1.0);
double b=2*(x1*1.0)*(x2*1.0)+2*(y1*1.0)*(y2*1.0)+2*(z1*1.0)*(z2*1.0);
double c=(x1*1.0)*(x1*1.0)+(y1*1.0)*(y1*1.0)+(z1*1.0)*(z1*1.0)-(r*1.0)*(r*1.0);
double d=b*b-4*a1*c;
if(d<0) continue;
double xx=(-b+sqrt(d))/(2*a1);
double yy=(-b-sqrt(d))/(2*a1);
if(xx<0&&yy<0) continue;
a[cnt].getime=min(xx,yy);
if(a[cnt].getime<0)  a[cnt].getime=0;;
a[cnt++].leftime=max(xx,yy);
}
sort(a,a+cnt,cmp);
ans=cnt;
res=0;
int k;
for(int i=0;i<cnt;i=k)
{
k=i+1;
for(int j=i+1;k<cnt;j++)
{
if(a[j].getime<=a[i].leftime)
k=j+1;
else
break;
}
res++;

}
printf("Case %d: %d %d\n",++cas,ans,res);
}
return 0;
}

490 篇文章45 人订阅

0 条评论

## 相关文章

### HDU2837 Calculation(扩展欧拉定理)

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Othe...

9420

### POJ----The Suspects

The Suspects Time Limit: 1000MS Memory Limit: 20000K Total Submissions: ...

366120

### hdu 4009 Transfer water（最小型树图）

Transfer water Time Limit: 5000/3000 MS (Java/Others)    Memory Limit: 65768/657...

37490

### POJ-1953 World Cup Noise（线性动规）

World Cup Noise Time Limit: 1000MS Memory Limit: 30000K Total Submissio...

35560

### HDUOJ-----1066Last non-zero Digit in N!

Last non-zero Digit in N! Time Limit: 2000/1000 MS (Java/Others)    Memory Limit...

33960

### POJ-2777 Count Color（线段树，区间染色问题）

Count Color Time Limit: 1000MS Memory Limit: 65536K Total Submissions: ...

35540

### HDUOJ--1159Common Subsequence

Common Subsequence Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536...

26970

### HDU 1103 Flo's Restaurant(模拟+优先队列)

Flo's Restaurant Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/...

28860

23170

### HDUOJ----（4706）Children's Day

Children's Day Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/327...

39680 