R03392
Point Strictly Inside a Simple Polygon
골드 IV레이팅
의견: 0
설명
단순 다각형(볼록이 아닐 수 있다)이 \(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
태그
평가 및 의견
Point Strictly Inside a Simple Polygon
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Point Strictly Inside a Simple Polygon
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기