UVa 10915

From Algorithmist
Jump to navigation Jump to search

10915 - War on Weather[edit]

Summary[edit]

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[edit]

Simple 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[edit]

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

Input[edit]

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

Output[edit]

2
3