Khoảng Cách Tới Mạng Lưới Cáp
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Đề bài
Một mạng lưới cáp ngầm gồm $N$ đoạn thẳng trên mặt phẳng. Có $Q$ trạm quan trắc, mỗi trạm tại một điểm $(x, y)$.
Với mỗi trạm quan trắc, hãy tìm khoảng cách Euclid ngắn nhất từ trạm đó tới ít nhất một đoạn cáp trong mạng lưới.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 1000$).
- $N$ dòng tiếp theo, mỗi dòng chứa $4$ số nguyên $x_1, y_1, x_2, y_2$ mô tả một đoạn cáp.
- $Q$ dòng tiếp theo, mỗi dòng chứa $2$ số nguyên $x, y$ là tọa độ một trạm quan trắc.
Dữ liệu ra
- Với mỗi trạm quan trắc, in ra khoảng cách ngắn nhất làm tròn đến $6$ chữ số thập phân trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 2 3 0 0 4 0 4 0 4 4 2 2 0 5 4 2 |
2.000000 4.123106 0.000000 |
Giới hạn
- $1 \le N, Q \le 1000$
- $|x|, |y| \le 10^6$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion