UVa 10078

10078 - The Art Gallery

• http://acm.uva.es/p/v100/10078.html

Summary

A polygon without any critical points is a convex polygon. This problem reduce to finding out rather a polygon is convex or not.

Explanation

It's easy to see (and prove) that a convex polygon satisfy the condition. An easy way to test if a polygon is convex or not is by walking the perimeter. If a polygon is a convex polygon, you can walk around the perimeter, and you will either keep turning left (counterclockwise) or turning right (clockwise). If a polygon does both, then there must be a reflex vertex, and thus not convex.

Gotcha's

• The order is not given, and needs to be figured out.

Input

4
0 0
3 0
3 3
0 3
4
0 0
3 0
1 1
0 3
0

Output

No
Yes