Đường Thẳng Đủ Đông · canuc80k5603

Có $n$ điểm phân biệt trên mặt phẳng tọa độ. Một đường thẳng được gọi là đủ đông nếu nó đi qua ít nhất

⌈ \frac{n \cdot p}{100} ⌉

điểm đã cho. Hãy xác định xem có tồn tại một đường thẳng đủ đông hay không.

Input

Dòng đầu chứa số nguyên $n$ - số điểm.
Dòng thứ hai chứa số nguyên $p$ - tỉ lệ phần trăm cần đạt.
Mỗi dòng trong $n$ dòng tiếp theo chứa hai số nguyên $x_{i}, y_{i}$ , là tọa độ của điểm thứ $i$ .

Output

In possible nếu tồn tại một đường thẳng đủ đông; ngược lại, in impossible.

Constraints

$1 \leq n \leq 1 0^{5}$ .
$20 \leq p \leq 100$ .
$0 \leq x_{i}, y_{i} \leq 1 0^{9}$ .
Không có hai điểm trùng nhau.
Ký hiệu ⌈z⌉ là số nguyên nhỏ nhất không nhỏ hơn $z$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 80$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

possible

Giải thích: Cần ít nhất $⌈ 6 \cdot 50/100 ⌉ = 3$ điểm. Ba điểm $(0, 1), (2, 5)$ và $(4, 9)$ cùng nằm trên đường thẳng $y = 2 x + 1$ , nên kết quả là possible.

Test 2

Input

Output

impossible

Giải thích: Ngưỡng cần đạt là $3$ điểm, trong khi mỗi đường thẳng qua các đỉnh của hình vuông đã cho chỉ chứa nhiều nhất $2$ điểm.

Ý tưởng: Một đường thẳng được xác định duy nhất bởi hai điểm phân biệt. Đặt need = ceil(n·p/100). Nếu need ≤ 2, bất kỳ một hoặc hai điểm đều nằm trên một đường thẳng nên đáp án chắc chắn là possible.
Ý tưởng: Với trường hợp còn lại, ta lặp 700 lần. Mỗi lần chọn đều hai chỉ số khác nhau, rồi quét toàn bộ tập điểm và đếm bằng tích chéo nguyên xem có bao nhiêu điểm nằm trên đường qua cặp vừa chọn. Nếu số đếm đạt need, ta trả lời ngay.
Ý tưởng: Nếu một đường tốt chứa k ≥ need điểm, xác suất một lần thử chọn cả hai đầu mút trên đường ấy là k(k-1)/(n(n-1)). Vì p ≥ 20, xác suất này xấp xỉ ít nhất 0.04 ở miền lớn. Xác suất trượt qua 700 lần nhỏ hơn (1-0.04)^700, dưới 4·10^-13. Mặt khác, mỗi đường ứng viên đều được đếm lại chính xác, nên thuật toán không bao giờ in possible sai.
Ý tưởng: Để tránh sai số số thực, ba điểm A, B, C được kiểm tra thẳng hàng bằng
Ý tưởng: (B.x-A.x)(C.y-A.y) = (B.y-A.y)(C.x-A.x).
Ý tưởng: Tích có thể lớn hơn 64 bit, vì vậy dùng __int128.
Ý tưởng: Độ phức tạp là O(700·n) thời gian và O(n) bộ nhớ.