Photo Shoot
Time limit1sMemory limit128 MB
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 : if he points the camera in a direction (measured in degrees from the -axis), then everything in the range from to 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 , , , : the number of people surrounding Adam (), Adam's location , and the field-of-view of his camera in degrees (). The maximum value of , , and is , and the maximum value of is .
This is followed by coordinate pairs giving the locations of the people (). No two people (including Adam) stand in the same spot. All locations use the standard Cartesian - 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 degrees apart from each other relative to Adam. Print each answer in the form Case k: x, where is the case number starting from 1 and is the minimum number of photos.