UVa 10078

From Algorithmist
Jump to navigation Jump to search

10078 - The Art Gallery[edit]

Summary[edit]

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

Explanation[edit]

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[edit]

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

Input[edit]

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

Output[edit]

No
Yes

Solutions[edit]