R & J

Interview

Time limit1sMemory limit128 MB

Summary

Given two ships and n spheres in 3D, count how many spheres the segment between the ships intersects.

Level: Medium6 of 10
Topics: Geometry, Math, Implementation, Brute force
Solved: No attempts yet

Problem

Long ago, Romy and Jules were separated by their parents and forbidden to ever see each other again. Using a tin-can telephone, their love survived. Generations later, Romy's great (times six) grandchild Julia (from the planet Mars) has fallen in love with Romian (from the planet Epsilon 186-Beta), but their parents' feud keeps them apart. To stop them from meeting, their parents put each of them on a spaceship with no long-range communication equipment, so Julia and Romian must trade Morse-code messages using a laser.

In their era a laser travels infinitely far through space, instantly, and a message gets through as long as the straight route between sender and receiver is not blocked. Assume every planet and spaceship is stationary.

Given the 3D grid coordinates of the two spaceships, determine how well they can communicate. Their laser is often blocked by planets that lie in the way. Count how many planets block the laser — that is, how many planets the segment joining the two spaceships passes through.

Input

The first two lines give the grid coordinates of Romian's and Julia's spaceships, respectively. Each coordinate is three whitespace-separated integers.

The next line contains a single integer $n$ ( $1 \le n \le 2000$ ), the number of planets in the current sector of space. Each of the following $n$ lines describes one planet with four whitespace-separated integers: the first three are the coordinates of the planet's center and the fourth is its radius. A planet with center $(a, b, c)$ and radius $r$ is the set of points satisfying $(x-a)^2 + (y-b)^2 + (z-c)^2 = r^2$ . You may assume $0 \le r \le 5000$ and, for every coordinate $(a, b, c)$ , $0 \le |a|, |b|, |c| \le 5000$ .

You may also assume the following:

Neither Romian nor Julia is within $10^{-8}$ units of a planet (they would crash into it), nor inside a planet (which is impossible).
Romian and Julia do not occupy the same position in space.
If the laser hits a planet, it would also hit a planet whose radius is $10^{-8}$ units smaller. If the laser misses a planet, it would also miss a planet whose radius is $10^{-8}$ units larger.

Output

Print a single integer $b$ ( $0 \le b \le n$ ), the number of planets that block the laser. Print 0 if no planet blocks it.

Examples4

Example 1

Input

100 100 100
-100 -100 -100
2
0 0 0 2
50 60 -50 5

Expected output

Example 2
Input
```
0 0 0
10 0 0
1
0 100 0 5
```
Expected output
```
0
```
Example 3
Input
```
0 0 0
20 0 0
1
10 0 0 1
```
Expected output
```
1
```

Example 4

Input

Expected output