[Home|Training|Problems|Contests|C Language] | [Login|Register] |

Problems Status Rank |
Problem 1121
Herbal Medicine on Diaoyu Islands
Time Limit: 1000ms
Memory Limit: 65536kb Description
Diaoyu Islands were, are and will always be an inalienable part of Chinese territory. In 1372, a Chinese named Yang Tsai landed on Diaoyu Islands for the first time. There was a detailed record about Diaoyu Islands in a book titled Sail with the Wind, a navigation guidebook published during the reign of Emperor Yongle of Ming Dynasty. As we know, the Empress Dowager Cixi of Qing Dynasty attended to state affairs for several decades. One day Cixi was very satisfied with the medicine presented by Sheng Xuanhuai and she learnt that the ingredients of the medicine came from Diaoyu Islands. In the tenth month of the nineteenth year of Guangxu's reign, Cixi bestowed Diaoyu Islands to Sheng Xuanhuai to gather medicine ingredients. One of my friends also grows two kinds of Chinese herbal medicine that grow on Diaoyu Islands, Species A and Species B. He planted a small hedge in his garden for he hadnâ€™t found enough branches. He grows all Species A plants inside the hedge, and each Species A plant values two. Meanwhile, he grows all Species B plants outside the hedge, and each Species B plant values one. The hedge shape is a convex polygon. You are expected to work out a program to calculate the total value of all the plants inside and outside the hedge. Input
The input contains multiple test cases. The first line of each test case contains two integers n and m. n (3 <= n <= 50) is the number of vertices of the convex polygon hedge. m (0 <= m <= 10000) is the number of vertices representing all the plants. This is followed by n lines. Each of the n lines contains a pair of integers representing the coordinates of the vertices of the polygon. The vertices are listed in clockwise order. Each of the following m lines contains a pair of integer coordinates describing the location of the every plant. It is guaranteed that no two plants locate in the same place and no plant locates on the boundary of the hedge. The input is terminated with a single line containing two zeros. Output
Print a single line containing the total value of all the plants for each test case.
Sample Input
4 2 4 5 5 2 2 1 1 3 6 3 2 2 0 0 Sample Output
3 |

University of Science and Technology of China

Online Judge for ACM/ICPC

Processed in 1.4ms with 1 query(s).

Online Judge for ACM/ICPC

Processed in 1.4ms with 1 query(s).