레이팅 미적용설명
단순 다각형(볼록이 아닐 수 있다)이 \(N\)개의 꼭짓점으로 순서대로 주어지고, 이어서 질의 점 \(Q\)가 주어진다. \(Q\)가 다각형의 내부에 엄격히 있는지 판별하시오. 경계 위의 점은 외부로 본다. 정수 외적을 이용한 반직선 교차(홀짝) 판정으로 부동소수점을 피할 수 있다. 엄격히 내부에 있으면 1, 아니면 0을 출력하시오.
제약
입력 형식
첫 줄에 \(N\) (\(3 \le N \le 2000\))이 주어진다. 다음 \(N\)개의 줄에 꼭짓점 \(x_i\ y_i\)가 순서대로 주어진다. 마지막 줄에 질의 점 \(x_Q\ y_Q\)가 주어진다. 모든 좌표는 \(-10^5 \le v \le 10^5\)이다.
출력 형식
점이 엄격히 내부에 있으면 1, 아니면 0을 출력한다.
예제 1
입력
4
0 0
4 0
4 4
0 4
2 2
출력
1
예제 2
입력
4
0 0
4 0
4 4
0 4
5 5
출력
0
예제 3
입력
4
0 0
4 0
4 4
0 4
2 0
출력
0
문제 정보
riseoj 작성
출처 RiseOJ Basics
태그