Solved by 17 users: fetetriste, Norbert, dan, svirg, DAV, zloy_mipt, popo, RAVEman, UdH-WiNGeR, defrager, aioni, FordPerfect, mazahaka, Dest, abortmozga.ru, avg79, regmar.
` <  <  <  <  <  <  <  <  <  < `

## Flight to Mars

Time limit = 1 second(s)

Memory limit = 64 Mb

In October 1, 203* the Only Superpower launches the first manned expedition to Mars on the Avenger spacecraft. To ensure safe landing on Mars, a robotic space probe orbiting Mars has dropped three beacons marking a safe landing area on the Martian surface.

However, to cut the cost of the expedition, Avenger is not equipped with a parachute. So Avenger just moves at a constant speed until the Martian surface is reached.

The taikonaut commander asks you to determine if Avenger hits the surface inside the safe landing area. This area is the spherical triangle with the apexes at the beacon landing points.

Input

The first input line contains three integer numbers (x0, y0, z0) — the Cartesian coordinates of the Martian center. The next input line contains one integer number R (1 ≤ R ≤ 10 000) — the radius of Mars.

The next three lines contain spherical coordinates of the beacons. Each coordinate is specified by two integer numbers d_i and l_i (-90 ≤ d_i ≤ 90, -180 ≤ l_i ≤ 180), where d_i is the latitude, l_i is the longitude, both measured in degrees. The north latitude is positive, and the south latitude is negative. The west longitude is positive, and the east longitude is negative. The next line contains the Cartesian coordinates (x1,y1,z1) of the Avenger starting point in the circummartian space The next line contains the direction (v_x,v_y,v_z) of the Avenger's movement.

All coordinates do not exceed 10000 by absolute value. The North Pole is towards (0, 0, 1) direction from the Martian center. The Prime Meridian crosses the Equator at (1, 0, 0) direction from the Martian center. The beacon landing points do not belong to one great circle. Also there exists a point in space, visible from all beacon landing points.

Since the spacecraft moves really fast, you may disregard the Martian rotation and orbital movement and think of it as a fixed sphere. Gravitational attraction of Mars is also considered negligible.

Output If Avenger successfully crashes inside or on the boundary of the safe landing area, output «YES», otherwise output «NO». It is guaranteed that if Avenger crashes outside of the safe landing area the distance between the crash point and the border of the safe landing area is at least R10-6.

 Input#1```0 0 0 1 0 0 90 0 0 90 1 1 1 -1 -1 -1 ``` Output#1```YES ```

Author:
ACM ICPC 2008-2009, Moscow Subregional Contest, Moscow, October 26, 2008
26 October 2008

 © acm.mipt DevGroupThe page was generated in 220ms