This page is still under construction.

Parts of this page are still being built. What you see may change.

Up Above the World So High

Interview

Time limit8sMemory limit512 MB

Summary
Given up to 100 star positions and an angular radius, find the maximum number of stars that fit inside a circular cone of that half-angle centered at the origin.
Level

Medium7 of 10

Topics
Geometry, Brute force, Sorting, Two pointers
Solved
No attempts yet

Problem

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

Children may ask their parents the same question aboard a spaceship billions of light-years away from Earth. Their telescopes are similar to ours and have a circular sight field. The telescope can be rotated freely, that is, the sight vector can take an arbitrary value.

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

Input

The first line of a test case contains a positive integer N not exceeding 100, the number of stars. Each of the N following lines contains three integers sx, sy and sz, giving the position (sx, sy, sz) of a star 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), the angular radius of the telescope's sight field in degrees. The telescope is at the origin of the coordinate system (0, 0, 0).

You may assume that changing 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.

Output

Output one line containing an integer, the maximum number of stars observable through the telescope. The output must contain no other characters.

Notes

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

Examples2

  1. Example 1

    Input
    2
    1 0 0
    0 1 0
    40
    
    Expected output
    1
    
  2. Example 2

    Input
    2
    1 0 0
    0 1 0
    50
    
    Expected output
    2