5097 : 다각형과 점
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
볼록 다각형의 $N$ 개 정점과 점 $(X, Y)$ 가 주어질 때, 점이 다각형 내부(경계 포함)에 있는지 판정하십시오.
[제약 조건]
• $3 \le N \le 100000$
• $-10^9 \leq X_i \leq 10^9$
• $-10^9 \leq Y_i \leq 10^9$
• $-10^9 \leq A \leq 10^9$
• $-10^9 \leq B \leq 10^9$
• 점 $(A, B)$ 는 다각형의 변 위에 있지 않습니다.
• 다각형의 내각이 정확히 $180^{\circ}$ 가 되는 경우는 없습니다.
• 입력되는 모든 값은 정수입니다.
[제약 조건]
• $3 \le N \le 100000$
• $-10^9 \leq X_i \leq 10^9$
• $-10^9 \leq Y_i \leq 10^9$
• $-10^9 \leq A \leq 10^9$
• $-10^9 \leq B \leq 10^9$
• 점 $(A, B)$ 는 다각형의 변 위에 있지 않습니다.
• 다각형의 내각이 정확히 $180^{\circ}$ 가 되는 경우는 없습니다.
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 $N$ 이 주어집니다.
출력 설명
내부 또는 경계에 있으면 `Yes`, 아니면 `No`를 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
0 0
4 0
0 3
1 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
Yes도움
벡터의 외적을 사용하여 점이 모든 변의 같은 쪽에 있는지 확인하십시오.