Line Game
Xem dạng PDF
Gửi bài giải
Điểm:
0,70 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho ~n~ điểm trên mặt phẳng ~Oxy~ và tham số ~p~.
Hãy xác định xem, có tồn tại một đường thẳng sao cho có ít nhất ~p~ phần trăm các điểm trong ~n~ điểm được cho nằm chính xác trên đường thẳng đó hay không.
Input
- Dòng đầu gồm số nguyên dương ~t~ miêu tả số bộ test.
- Mỗi bộ test bao gồm:
- Dòng đầu gồm số nguyên dương ~n~.
- Dòng thứ hai gồm số nguyên dương ~p~.
- ~n~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~.
Đảm bảo rằng không có hai điểm nào trùng khớp.
Output
- Với mỗi bộ test, nếu tồn tại đường thẳng thỏa mãn thì in ra "possible", ngược lại in ra "impossible".
Constraints .
- ~1 \le t \le 5~.
- ~1 \le n \le 10^5~.
- ~35 \le p \le 100~
- Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^9,10^9]~.
Sample Input 1
2
5
55
0 0
10 10
10 0
0 10
3 3
5
45
0 0
10 10
10 0
0 10
3 4
Sample Output 1
possible
impossible
Explanation 1
Ở ví dụ ~1~, tồn tại đường thẳng đi qua (ít nhất) ~3~ điểm trong số ~5~ điểm trên.
Ở ví dụ ~2~, không tồn tại đường thẳng nào đi qua nhiều hơn hoặc bằng ~45\%~ số điểm.
Bình luận
Spoil ⚠️