
ZOJ Problem Set  1999
Two points p and q inside a simple polygon P are mutually visible, if the line segment connecting p and q does not include any point outside P. The points on the boundary edges of P are considered to be inside P. Two sets of points are said to be mutually weakly visible, if for each point in one set, there will be a point in the other set such that the two points are mutually visible. Given two distinct points s and t on the boundary of P, P is said to be a street polygon with respect to s and t, if the two boundary chains from s to t are mutually weakly visible. For example, the following figure shows a simple polygon which is a street and one which is not. You are to write a program that given a simple polygon P with vertices v1, v2, ��, vn, determines if P is a street polygon with respect to vj and vk (which are two given distinct vertices of P).
Source: Asia 2003, Tehran (Iran), Preliminary 