ZOJ Problem Set - 3491
We are from the kingdom of decayeds, to help the human innovate, and get the suffer away, all we need is your brain! -- by Zombies
Your garden is consisted of several lanes. The zombies are moving along the lanes in your garden. But as they are moving very slowly, you can assume they are still. The wall-nuts are thrown out one after another. That is to say, a wall-nut will not be thrown out until the previous one goes out of the garden. Each wall-nut goes along the lane from left to right at first. After hitting the first zombie, it will go diagonally at 45 degree, in the direction which is farther from the edge. For example, if there are 4 lanes numbered from 1 to 4 from top to bottom, a wall-nut from lane 3 will go upper right after hitting the first zombie, while the one from lane 2 or lane 1 will go bottom right. To simplify the case, you can assume that the number of lanes is always even so that you can determine the direction after the first hit. After that, the wall-nut will reflect if it hits another zombie or hit the upper edge of bottom edge of the garden. That means a wall-nut which goes upper right originally will go bottom right after the reflection and vice versa. Each zombie can be defeated by one hit of a wall-nut. If there are several zombies standing at the same place, one hit can defeat only one of them.
Given the place of each zombie and the lane each wall-nut goes, you are asked to calculate the number of zombies that are defeated by the wall-nuts.
There are multiple test cases. The first line of input is an integer T ≈ 100 indicating the number of test cases.
The first line of each test case contains 3 integers N, M and K, indicating the number of lanes, the number of zombies and the number of wall-nuts (0 < N ≤ 2000, 0 < M ≤ 200000, 0 < K ≤ 100000). M lines follow, each of which contains 2 integers xi and yi(0 < xi ≤ 1000000, 1≤ yi ≤ N), describing the coordinates of the i-th zombie. Then K lines follow, each of which contains 1 integer ci(1 ≤ ci ≤ N), the number of lane where the i-th wall-nut is put.
Output the number of zombies that are defeated in one line.
4 2 2 1 1 1 1 1 1 2 1 2 1 1 1 1 4 2 1 1 2 2 3 2 4 2 1 1 1 5 3 1
1 1 2 2
In the last sample, the wall-nut hit zombie at (1, 1) and then go through (2, 2), (3, 3), (4, 4), and hit the second zombie at (5, 3).
Author: GUAN, Yao
Contest: The 8th Zhejiang Provincial Collegiate Programming Contest