시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 256 MB 318 60 39 22.674%

문제

N개의 점이 좌표 평면 상에 있을 때, 이 중 p 퍼센트 이상의 점들을 지나는 직선이 존재하는지 판별하시오. 즉, 0.01Np개 이상의 점을 지나는 직선이 존재하는지를 판별하시오.

입력

입력은

  • 첫번째 줄에 점의 수 n (1 ≤ n ≤ 105)
  • 두번째 줄에 직선이 지나야 하는 점의 퍼센티지 p (20 ≤ p ≤ 100)
  • 이후 n개의 줄에 점의 좌표 x, y (0 ≤ x, y ≤ 109)

의 형태로 주어진다. 

주어지는 모든 점들은 서로 다르다.

출력

그러한 직선이 존재하면 possible, 존재하지 않는다면 impossible을 출력한다.

예제 입력

5
55
0 0
10 10
10 0
0 10
3 3

예제 출력

possible

예제 입력 2

5
45
0 0
10 10
10 0
0 10
3 4

예제 출력 2

impossible

힌트

입력 예제 1에서 (0, 0) / (3, 3) / (10, 10)을 지나는 직선을 찾을 수 있다. 2.75개 이상의 점을 지났으니 그러한 직선이 있다고 볼 수 있다.