[BOJ/Platinum 3] 백준 27656 양궁(C++)
·
BOJ/Platinum ~ Diamond
문제 링크 https://www.acmicpc.net/problem/27656 문제 평면 위에 N개의 점이 있다. 남은 점이 없을 때까지 다음 시행을 반복하여 과녁을 만든다. 남은 점들을 모두 포함하는 가장 작은 볼록 다각형을 얻는다. 볼록 다각형 경계에 있는 점들을 제거한다. 한 점이 남거나 남은 점들이 한 직선 위에 있는 경우는 없다. 또한, 볼록 다각형 경계에 있는 어느 세 점도 한 직선 위에 있지 않음이 보장된다. 얻은 도형을 순서대로 P1, P2, ⋯, Pk라 할 때, 화살의 점수는 화살이 꽂힌 위치가 P1 외부이면 0, P1 내부이면서 P2 외부이면 1, ⋯, Pk−1 내부이면서 Pk 외부이면 k−1, Pk 내부이면 k이다. 도형의 내부는 경계를 포함한다. Q번 화살을 쏠 때, 각각의 점수를 ..