시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 199 | 67 | 43 | 32.331% |
병찬이는 아주아주 큰 크기의 파인애플 피자를 가지고 있다. 이 파인애플 피자는 매우 크기 때문에, 무한 2차원 평면이라고 가정해도 좋다. 이 피자에는 맛있는 파인애플 조각이 n개가 있는데, 병찬이와 친구들은 파인애플을 매우 좋아하기 때문에 모두가 똑같은 개수의 파인애플 조각을 가질 수 있도록 피자를 나누려고 한다.
n개의 파인애플 조각들이 각각 점 P1, P2, P3,...,Pn으로 주어진다고 하자. (파인애플 조각은 넓이가 없는 하나의 점으로 봐도 무방하다.) 그리고 점 Q와 병찬이와 친구들의 수 k가 주어진다.
병찬이는 점 Q를 시작점으로 하는 반직선 k개를 그어서, 이 파인애플 피자를 k개로 쪼개려고 하는데, 각 피자 조각의 파인애플 조각들이 같은 개수가 되도록 자르고 싶다. 단, 파인애플의 맛을 온전히 보존하기 위해, 각 피자 조각의 경계선에 파인애플이 걸치는 일은 없어야 한다.
이 조건을 만족하도록 반직선 k개를 그을 수 있는지 판단하는 프로그램을 작성하시오.
첫 번째 줄에 점 P들의 개수 n과 병찬이와 친구들의 수 k가 주어진다. (2 ≤ n, k ≤ 8,000)
두 번째 줄부터 n + 1번째 줄까지 점 P의 좌표가 주어진다.
i + 1번째 줄에는 Pi의 x 좌표, Pi의 y좌표가 주어진다.
n + 2번째 줄에는 점 Q의 x 좌표, 점 Q의 y 좌표가 주어진다.
모든 P, 그리고 Q는 좌표가 다르다. 즉, 어느 두 점도 겹치지 않는다.
모든 P, 그리고 Q의 x, y 좌표 값은 −105 이상 105 이하의 값을 가지는 정수다.
조건을 만족하도록 반직선을 그을 수 있으면 YES, 아니면 NO를 출력한다.
6 3 -2 0 1 1 3 3 -4 -4 -2 4 4 -2 0 0
YES
다음 그림을 참조하자.
University > POSTECH > PPC 2018 E번