Khoảng Cách Giữa Hai Đa Giác Lồi
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Đề bài
Cho hai đa giác lồi $P$ (gồm $N$ đỉnh) và $Q$ (gồm $M$ đỉnh), mỗi đa giác được liệt kê theo thứ tự ngược chiều kim đồng hồ.
Hãy tính khoảng cách Euclid ngắn nhất giữa một điểm bất kỳ thuộc $P$ (kể cả phần bên trong) và một điểm bất kỳ thuộc $Q$ (kể cả phần bên trong). Nếu hai đa giác giao nhau hoặc chạm nhau, khoảng cách bằng $0$.
Gợi ý: Sử dụng tổng Minkowski $P \oplus (-Q)$ trong $O(N + M)$ rồi tính khoảng cách từ gốc tọa độ $(0, 0)$ tới đa giác lồi kết quả.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$ ($3 \le N, M \le 10^5$).
- $N$ dòng tiếp theo chứa tọa độ các đỉnh của đa giác $P$ theo thứ tự ngược chiều kim đồng hồ.
- $M$ dòng tiếp theo chứa tọa độ các đỉnh của đa giác $Q$ theo thứ tự ngược chiều kim đồng hồ.
Dữ liệu ra
- In ra một số thực là khoảng cách ngắn nhất giữa $P$ và $Q$, làm tròn đến $6$ chữ số thập phân.
Ví dụ
| Input | Output |
|---|---|
| 4 4 0 0 2 0 2 2 0 2 5 0 7 0 7 2 5 2 |
3.000000 |
Giới hạn
- $3 \le N, M \le 10^5$
- $|x|, |y| \le 10^7$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion