시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 94 33 19 35.849%

문제

병찬이는 아주아주 큰 크기의 파인애플 피자를 가지고 있다. 이 파인애플 피자는 매우 크기 때문에, 무한 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를 출력한다.

예제 입력 1

6 3
-2 0
1 1
3 3
-4 -4
-2 4
4 -2
0 0

예제 출력 1

YES

힌트

다음 그림을 참조하자.


 

출처

University > POSTECH > PPC 2018 E번

  • 문제의 오타를 찾은 사람: doju
  • 문제를 만든 사람: hyperbolic