Good Circle
Xem dạng PDF
Gửi bài giải
Điểm:
0,20 (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
Trên trục tọa độ ~Oxy~, cho tọa độ điểm ~I~. Có ~n~ đoạn thẳng và một số nguyên ~k~, đoạn thứ ~i~ có hai đầu mút là ~2~ điểm ~A_i~ và ~B_i~. Đường tròn có tâm ~I~ và bán kính ~R~ với ~R~ là số nguyên không âm, gọi tắt là ~(I,R)~, được gọi là tốt nếu chỉ có bé hơn hoặc bằng ~k~ đoạn thẳng có điểm nằm bên trong hoặc bên trên đường tròn.
Hãy tìm số nguyên không âm ~R~ lớn nhất sao cho đường tròn ~(I,R)~ là tốt.
Input
- Dòng đầu gồm hai số nguyên ~x_I,y_I~ miêu tả tọa độ của điểm ~I~.
- Dòng thứ hai gồm ~2~ số nguyên dương ~n~ và ~k~.
- ~n~ dòng sau, mỗi dòng gồm hai cặp số nguyên: ~x_{A_i},y_{A_i}~ và ~x_{B_i},y_{B_i}~ là hai đầu mút của đoạn thẳng thứ ~i~.
Output
- In ra ~R~ là kết quả của bài toán.
Constraints .
- ~1 \le k < n \le 10^5~.
- Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.
Subtask
- Sub ~1~ (~50\%~): ~n \le 1000~ và tọa độ của các điểm đều nằm trong khoảng ~[-10^3,10^3]~.
- Sub ~2~ (~50\%~): Không giới hạn gì thêm.
Sample Input 1
0 0
4 2
-4 4 1 5
-3 2 -1 1
2 2 6 4
-3 -2 -1 -4
Sample Output 1
3
Explanation 1
Đường tròn tâm ~A~ với bán kính là ~3~ gồm ~2~ đoạn thẳng có điểm nằm bên trong hoặc bên trên đường tròn là ~DE~ và ~FG~, đây là bán kính lớn nhất thỏa mãn.
Bình luận
Bên trên đường tròn là sao nhỉ các bạn? Mình thấy đoạn thẳng BC có đầu mút nằm TRÊN đường tròn (I; R) mà ?
Bên trên đường tròn tức là điểm đó thuộc cái đường tròn (I; R) (Ví dụ ở hình trên đề bài, ta có điểm (0; 3) thuộc đường tròn / nằm trên đường tròn). Còn đoạn thằng BC có đầu mút nằm ngoài đường tròn.
Cảm ơn bạn
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.