Algorithm 版 (精华区)

发信人: xiong (阿拉斯加棕熊), 信区: Algorithm
标  题: 1081P-Points Within-ZJU
发信站: 哈工大紫丁香 (2002年10月13日21:01:11 星期天), 站内信件

Points Within
----------------------------------------------------------------------------
----
Time limit: 30 Seconds   Memory limit: 32768K
Total Submit: 189   Accepted Submit: 49
----------------------------------------------------------------------------
----
Statement of the Problem
Several drawing applications allow us to draw polygons and almost all of the
m allow us to fill them with some color. The task of filling a polygon reduc
es to knowing which points are inside it, so programmers have to colour only
 those points.
You're expected to write a program which tells us if a given point lies insi
de a given polygon described by the coordinates of its vertices. You can ass
ume that if a point is in the border of the polygon, then it is in fact insi
de the polygon.
Input Format
The input file may contain several instances of the problem. Each instance c
onsists of: (i) one line containing integers N, 0 < N < 100 and M, respectiv
ely the number of vertices of the polygon and the number of points to be tes
ted. (ii) N lines, each containing a pair of integers describing the coordin
ates of the polygon's vertices; (iii) M lines, each containing a pair of int
eger coordinates of the points which will be tested for "withinness" in the 
polygon.
You may assume that: the vertices are all distinct; consecutive vertices in 
the input are adjacent in the polygon; the last vertex is adjacent to the fi
rst one; and the resulting polygon is simple, that is, every vertex is incid
ent with exactly two edges and two edges only intersect at their common endp
oint. The last instance is followed by a line with a 0 (zero).
Output Format
For the ith instance in the input, you have to write one line in the output 
with the phrase "Problem i:", followed by several lines, one for each point 
tested, in the order they appear in the input. Each of these lines should re
ad "Within" or "Outside", depending on the outcome of the test. The output o
f two consecutive instances should be separated by a blank line.
Sample Input
3 1
0 0
0 5
5 0
10 2
3 2
4 4
3 1
1 2
1 3
2 2
0
Sample Output
Problem 1:
Outside
Problem 2:
Outside
Within

--

                    为了民族的尊严    为了祖国的明天

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.226.228]