Alien PandemiaProblem code: ALNPD |
All submissions for this problem are available.
The current year is 2210, and the humanity is in great danger. An alien race has discovered us and wants to cleanse this planet from our presence, so they can take all our natural resources to their planet. However, they are physically weak, so their plan consists in infecting one human with the T-virus, which is highly contagious but not deadly. If at any point of time, one person is at a distance not greater than R from a person infected with the T-virus, then he/she will be infected with the B-virus, which will kill him/her instantly.
The Terra Disease Control Center (TDCC) has discovered the aliens' plan, and they are determined to stop it. The first step is to create a simulation program that given the position of some static uninfected persons and the trajectory of a person infected with the T-virus, determines how many persons will be killed by the B-virus.
The trajectory followed by the infected person will be a polyline. A polyline is defined by M points Pi, and consists of the line segments between P1 and P2, P2 and P3, and so on. It is possible for a polyline to only have one point; in the simulator this will represent a static infected person.
Input
The first line contains an integer T, which species the number of test cases. Then, T test case descriptions will follow.
Each test case will start with a line with three positive integers, N, M and R, which specify the number of static uninfected persons, the number of points in the polyline that defines the movement of the infected person and the infection radius, respectively. The next N lines will contain two integers Xi and Yi, specifying the position of the uninfected person i. The next M lines will contain two integers Pxj and Pyj , specifying the point j that defines the trajectory of the infected person.
Output
For each input case you must print the string "Case #i: ", where i is the test case number, starting from 1, followed by the number of uninfected persons killed by the B-virus.
Example
Input: 2 4 1 4 2 2 1 5 -2 3 7 0 3 0 5 3 4 2 2 1 5 -2 3 -4 4 7 0 -3 0 3 0 0 3 Output: Case #1: 2 Case #2: 4
Constraints:
- T will be between 1 and 200, inclusive.
- N will be between 1 and 100, inclusive.
- R will be between 1 and 1000, inclusive.
- Xi will be between -1000 and +1000, inclusive, for all i between 1 and N, inclusive.
- Yi will be between -1000 and +1000, inclusive, for all i between 1 and N, inclusive.
- Pxj will be between -1000 and +1000, inclusive, for all j between 1 and M, inclusive.
- Pyj will be between -1000 and +1000, inclusive, for all j between 1 and M, inclusive.
- No pair of points in each test case will be equal.
- M will be between 1 and 100, inclusive.
| Author: | divij |
| Date Added: | 29-09-2010 |
| Time Limit: | 0.5 sec |
| Source Limit: | 50000 Bytes |
| Languages: | C, CLOJ, CPP 4.0.0-8, CPP 4.3.2, F#, GO, PERL6, PYTH 3.1.2, TEXT |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
HELP
Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:
- Accepted
Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark. - Time Limit Exceeded
Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach. - Wrong Answer
Your program compiled and ran succesfully but the output did not match the expected output. - Runtime Error
Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section. - Compilation Error
Your code was unable to compile. When you see this icon, click on it for more information.
If you are still having problems, see a sample solution here.
