War on Weather
Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 300 Accepted
Submission(s): 162
Problem Description
After an unprovoked hurricane attack on the south
shore, Glorious Warrior has declared war on weather. The first salvo in this
campaign will be a coordinated pre-emptive attack on as many tropical
depressions as possible. GW reckons that the attack will neutralize the tropical
depressions before they become storms, and dissuade others from
forming.
GW has at his disposal k space-to-earth killer satellites at
various locations in space. m tropical depressions are known to exist at various
locations on the earth‘s surface. Each satellite can attack any number of
targets on the earth provided there is line of sight between the satellite and
each target. How many different targets can be hit?
Input
The input consists of several test cases. Each case
begins with a line containing integers 0 < k, m &le 100 as defined above.
k lines follow, each giving x,y,z - the location in space of a satellite at the
scheduled time of attack. m lines then follow, each giving x,y,z - the location
of a target tropical depression. Assume the earth is a sphere centred at (0,0,0)
with circumference 40,000 km. All targets will be on the surface of the earth
(within 10-9 km) and all satellites will be at least 50 km above the surface. A
line containing 0 0 follows the last test case.
Output
For each test case, output a line giving the total
number of targets that can be hit. If a particular target falls within 10-8 km
of the boundary between being within line-of-sight and not, it may be counted
either way. (That is, you need not consider rounding error so long as it does
not exceed 10-8 km.)
Sample Input
3 2
-10.82404031 -1594.10929753 -6239.77925152
692.58497298 -5291.64700245 4116.92402298
3006.49210582 2844.61925179 5274.03201053
2151.03635167 2255.29684503 5551.13972186
-1000.08700886 -4770.25497971 4095.48127333
3 4
0 0 6466.197723676
0 6466.197723676 0
6466.197723676 0 0
6366.197723676 0 0
6365.197723676 112.833485488 0
0 0 6366.197723676
0 -6366.197723676 0
0 0
Sample Output
Source
Recommend
Eddy | We have
carefully selected several similar problems for you:
1145 1142 1154 1144 1143
计算几何的水题。
没有用到复杂的算法，用基本的几何知识即可解决这道题。
题意：给你k个卫星的坐标，m个目标的坐标（在地球上），问能这些卫星能击中几个目标。卫星只能击中面对着地球的那一面，背对着它的那一面无法击中。
思路：如果
卫星到目标的距离 >
卫星到切点的距离（作卫星到地球的切线，切线与地球的交点为切点），说明目标在当前卫星面对的地球的背面，无法击中。
代码：
1 #include <iostream>
2 #include <cmath>
3 using namespace std;
4 //#define PI 3.1415926
5 #define PI acos(-1.0) //产生精确的圆周率PI
6 struct Point3{
7 double x,y,z;
8 };
9 double dist3(Point3 p0,Point3 p1)
10 {
11 return sqrt((p1.x-p0.x)*(p1.x-p0.x) + (p1.y-p0.y)*(p1.y-p0.y) + (p1.z-p0.z)*(p1.z-p0.z));
12 }
13 Point3 K[110];
14 int main()
15 {
16 int k,m;
17 while(cin>>k>>m){
18 if(k==0 && m==0) break;
19 double r = 40000.0 / (2 * PI); //地球半径
20 int i;
21 for(i=1;i<=k;i++)
22 cin>>K[i].x>>K[i].y>>K[i].z;
23 int sum = 0; //记录有几个目标能被打击到
24 for(i=1;i<=m;i++){
25 Point3 M; //目标
26 cin>>M.x>>M.y>>M.z;
27 Point3 o; //地球球心
28 o.x=0,o.y=0,o.z=0;
29 int j;
30 for(j=1;j<=k;j++){ //看哪个卫星能打到目标，找到了就立刻退出循环
31 double k2o = dist3(K[j],o); //当前卫星到地球球心的距离
32 double k2m = dist3(K[j],M); //卫星到目标的距离
33 if( k2m*k2m <= k2o*k2o-r*r )
34 break;
35 }
36 if(j<=k)
37 sum++;
38 }
39 cout<<sum<<endl;
40 }
41 return 0;
42 }
Freecode : www.cnblogs.com/yym2013
hdu 1140:War on Weather（计算几何，水题）,布布扣,bubuko.com
hdu 1140:War on Weather（计算几何，水题）
原文：http://www.cnblogs.com/yym2013/p/3632793.html
