# UVa 10915

## Summary

Given a sphere (the Earth), a set of points S (satellites) outside the sphere and a set of points T (targets) on the boundary of the sphere, determine how many points in T are "visible" from at least one point in S.

## Explanation

Simple ${\displaystyle O(km)}$ algorithm works. For each point in T, check whether it's visible from every point in S.

A point P is visible from point Q, if the shortest distance from the line segment PQ to the sphere's center is greater than or equal to the sphere's radius.

Actually an easier way is to use dot product and find out whether the angle is acute or obtuse.

## Trivia

GW, perhaps, could also mean George W. (Bush) ;)

## 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
```

```2
3
```