Khoảng Cách Giữa Hai Đa Giác Lồi

Buổi 61 — Hình học tính toán
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề 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
Draft saved