Up Above the World So High

Time Limit : 8 sec, Memory Limit : 131072 KB

Problem K: Up Above the World So High

One of the questions children often ask is "How many stars are there in the sky?" Under ideal conditions, even with the naked eye, nearly eight thousands are observable in the northern hemisphere. With a decent telescope, you may find many more, but, as the sight field will be limited, you may find much less at a time.

Children may ask the same questions to their parents in a spaceship billions of light-years away from the Earth. Their telescopes are similar to ours with circular sight field. It can be rotated freely, that is, the sight vector can take an arbitrary value.

Given a set of positions of stars and the spec of a telescope, your task is to determine the maximum number of stars that can be seen through the telescope at a time.


The first line of a test case contains a positive integer N not exceeding 100, meaning the number of stars. Each of the N lines following it contains three integers, sx, sy and sz. They give the position (sx, sy, sz) of the star described in Euclidean coordinates. You may assume that -1000 ≤ sx ≤ 1000, -1000 ≤ sy ≤ 1000, -1000 ≤ sz ≤ 1000 and (sx, sy, sz) ≠ (0, 0, 0).

Then comes a line containing a positive integer ψ (0 < ψ < 90), which represents the angular radius, in degrees, of the sight field of the telescope. The telescope is at the origin of the coordinate system (0, 0, 0).

You may assume that change of the angular radius ψ by less than 0.01 degrees does not affect the answer, and that ∠POQ is greater than 0.01 degrees for any pair of distinct stars P and Q and the origin O.


One line containing an integer meaning the maximum number of stars observable through the telescope should be output. No other characters should be contained in the output.

Sample Input 1

1 0 0
0 1 0

Output for the Sample Input 1


Sample Input 2

1 0 0
0 1 0

Output for the Sample Input 2



This problem statement is taken from "How I Wonder What You Are!" in ACM-ICPC Asia Regional Contest 2006, Yokohoma, with small but substantial changes.

Source: ACM-ICPC Japan Alumni Group Winter Camp , Day 2, Tokyo, Japan, 2009-02-22