cho.sh양궁
아직 제출이 없습니다시간 제한2초메모리 제한1024 MB문제 설명
예제1
문제
평면 위에 N개의 점이 있다. 남은 점이 없을 때까지 다음 시행을 반복하여 과녁을 만든다.
- 남은 점들을 모두 포함하는 가장 작은 볼록 다각형을 얻는다.
- 볼록 다각형 경계에 있는 점들을 제거한다.
한 점이 남거나 남은 점들이 한 직선 위에 있는 경우는 없다. 또한, 볼록 다각형 경계에 있는 어느 세 점도 한 직선 위에 있지 않음이 보장된다.
얻은 도형을 순서대로 P_1,P_2,⋯,P_k라 할 때, 화살의 점수는 화살이 꽂힌 위치가 P_1 외부이면 0, P_1 내부이면서 P_2 외부이면 1, ⋯, P_k−1 내부이면서 P_k 외부이면 k−1, P_k 내부이면 k이다. 도형의 내부는 경계를 포함한다.
Q번 화살을 쏠 때, 각각의 점수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 점의 개수 N이 주어진다. (3≤N≤1,000)
둘째 줄부터 N개의 줄에 걸쳐 각 점의 좌표를 나타내는 −109 이상 109 이하의 두 정수가 공백을 사이에 두고 주어진다.
그다음 줄에 화살을 쏘는 횟수 Q가 주어진다. (1≤Q≤1,000,000)
그다음 줄부터 Q개의 줄에 걸쳐 화살이 꽂힌 위치의 좌표를 나타내는 −109 이상 109 이하의 두 정수가 공백을 사이에 두고 주어진다.
출력
화살의 점수를 한 줄에 하나씩 출력한다.