This page is still under construction.

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

Gypsy Moths

Time limit1sMemory limit128 MB

Summary
Given tree directions from a fixed camera and a fixed angular width, find the tenth-of-a-degree angle centered on the most trees, counting only trees strictly inside the view.
Level

Medium6 of 10

Topics
Two pointers, Sorting, Geometry, Math
Solved
No attempts yet

Problem

A ranger and a park manager are tracking gypsy-moth infestations in a park. A remote-controlled camera sits atop a nearby mountain, and every infested tree has been plotted as a point on a map.

Because the temperature on the mountain is dropping, the camera will soon freeze in place and can no longer be turned. It also has a narrow field of view, so it can only show trees that fall inside a limited angular range. Before the camera freezes, the ranger wants to aim it in the single direction that shows as many infested trees as possible.

The camera is at a fixed point. Distance does not affect visibility: a tree is visible as long as its direction from the camera falls within the camera's field of view.

Input

The input contains one or more data sets.

Each data set begins with a line containing a single non-negative integer NN, the number of infested trees. A line containing 00 marks the end of the input and must not be processed.

For a data set with N≥1N \ge 1:

  • The next line contains three floating-point numbers: the camera's XX and YY coordinates and the camera's field of view VV (an angle in degrees).
  • Each of the following NN lines contains the XX and YY coordinates of one infested tree. No tree shares the camera's coordinates.

All coordinates are floating-point numbers in the range −500.0-500.0 to 500.0500.0. The field of view VV is a floating-point number in the range 0.10.1 to 179.9179.9 degrees.

Output

For each data set, aim the camera at an angle AA that maximizes the number of infested trees lying within the angular range A±V/2A \pm V/2.

  • Angles are measured so that 0.00.0 points along the positive YY axis and 90.090.0 points along the positive XX axis (angles increase clockwise).
  • The camera clicks into place only at whole tenths of a degree, so AA must be a multiple of 0.10.1. Intermediate angles are not possible.
  • A tree counts as visible only if its direction lies strictly inside the range A±V/2A \pm V/2; a tree exactly on the boundary is not visible.
  • Distance does not affect visibility.
  • If several angles show the same maximal number of trees, choose the smallest such angle.

For each data set, print one line in exactly this form:

Point the camera at angle ### to view ## infested trees.

where ### is the chosen angle AA, in the range 0.00.0 to 359.9359.9, printed with exactly one digit after the decimal point, and ## is the number of visible trees, printed as an integer.

The test data are chosen so that no tree lies within 0.010.01 degree of a boundary, so borderline precision is never an issue.

Examples2

  1. Example 1

    Input
    5
    25.0 25.0 45.0
    25.5 35.0
    35.0 30.0
    45.0 45.0
    40.0 48.5
    20.0 18.0
    0
    
    Expected output
    Point the camera at angle 22.6 to view 3 infested trees.
    
  2. Example 2

    Input
    1
    0.0 0.0 90.0
    0.0 100.0
    1
    0.0 0.0 30.0
    100.0 0.0
    2
    0.0 0.0 60.0
    0.0 -100.0
    -100.0 0.0
    0
    
    Expected output
    Point the camera at angle 0.0 to view 1 infested trees.
    Point the camera at angle 75.1 to view 1 infested trees.
    Point the camera at angle 150.1 to view 1 infested trees.