Photo Shoot

Time limit1sMemory limit128 MB

Summary
Given Adam's position, each person's angle around him, and a fixed camera width, find the fewest photos that cover every person.
Level

Medium6 of 10

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

Problem

Adam Ansels is a photographer who specializes in impromptu photos of his clients. Right now Adam is standing in the middle of a field, surrounded by a large group of people.

Adam's camera has a fixed field-of-view angle ff: if he points the camera in a direction dd (measured in degrees from the xx-axis), then everything in the range from d−f/2d - f/2 to d+f/2d + f/2 appears in the picture.

Adam wants to take as few pictures as possible. Given the locations of the people around Adam and the camera's field-of-view angle, determine the minimum number of photos Adam must take so that everyone appears in at least one photo.

Input

Each test case starts with a line containing four integers nn, xx, yy, ff: the number of people surrounding Adam (n≥0n \ge 0), Adam's location (x,y)(x, y), and the field-of-view of his camera in degrees (f>0f > 0). The maximum value of nn, ∣x∣|x|, and ∣y∣|y| is 100100, and the maximum value of ff is 180180.

This is followed by nn coordinate pairs xi yix_i\ y_i giving the locations of the nn people (∣xi∣,∣yi∣≤1000|x_i|, |y_i| \le 1000). No two people (including Adam) stand in the same spot. All locations use the standard Cartesian xx-yy coordinate system.

A line consisting of four zeros terminates the input.

Output

For each test case, output the case number followed by the minimum number of photos Adam needs so that everyone appears in at least one picture. You may assume that no two people are exactly ff degrees apart from each other relative to Adam. Print each answer in the form Case k: x, where kk is the case number starting from 1 and xx is the minimum number of photos.

Examples2

  1. Example 1

    Input
    6 5 5 90
    1 4 5 10 6 9 7 4
    8 6 10 6
    20 20 20 180
    1 21 3 21 5 21 7 21 9 21 11 21 13 21 15 21 17 21 19 21
    21 21 23 21 25 21 27 21 29 21 31 21 33 21 35 21 37 21 39 21
    0 0 0 0
    
    Expected output
    Case 1: 3
    Case 2: 1
    
  2. Example 2

    Input
    1 0 0 90
    3 3
    4 0 0 80
    10 0 0 10 -10 0 0 -10
    0 0 0 0
    
    Expected output
    Case 1: 1
    Case 2: 4