점과 볼록 다각형 포함 관계

점과 볼록 다각형 포함 관계

볼록 다각형과 한 점이 주어질 때, 점이 다각형의 내부, 경계, 외부 중 어디에 있는지 판별하라.

다각형의 꼭짓점은 반시계 방향 순서로 주어진다. 볼록 다각형은 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형이다.

제한

• 3 ≤ N ≤ 100,000
• -10^9 ≤ x, y ≤ 10^9
• 모든 좌표는 정수이다.
• 꼭짓점이 일직선 위에 놓이는 경우는 없다.