HDU 1140 War on Weather （三维点之间距离）

大意：地球球心是(0,0,0)，给你k个卫星以及k个卫星的三维坐标(以球心为基准)，m个地球上的点以及m个点的三维坐标(以球心为基准)，问有多少个点是能被卫星覆盖到的，输出数量。

思路：

求出卫星与地球切线的长度，在地球上，与卫星连线的长度小于切线长度的肯定都能看到。

 1 #define pi acos(-1.0)
 2 
 3 struct point {
 4     double x, y, z;
 5 } P[110];
 6 
 7 double distance(point a, point b)
 8 {
 9     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
10 }
11 
12 int n, m;
13 
14 void Solve()
15 {
16     double R = 20000.0/pi;
17 
18     while(~scanf("%d%d", &n, &m))
19     {
20         if(!n && !m)
21         {
22             break;
23         }
24         for(int i = 0; i < n; ++i)
25         {
26             scanf("%lf%lf%lf", &P[i].x, &P[i].y, &P[i].z);
27         }
28 
29         int cnt = 0;
30         point pp;
31         for(int i = 0; i < m; ++i)
32         {
33             scanf("%lf%lf%lf", &pp.x, &pp.y, &pp.z);
34             for(int j = 0; j < n; ++j)
35             {
36                 double D2 = P[j].x*P[j].x+P[j].y*P[j].y+P[j].z*P[j].z;
37                 double L2 = D2-R*R;
38                 if(distance(P[j], pp) <= L2)
39                 {
40                     cnt++;
41                     break;
42                 }
43             }
44         }
45         printf("%d
", cnt);
46     }
47 }

HDU 1140