Rào Vườn

Xem dạng PDF

Gửi bài giải

Điểm: 1,07 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
(none)
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bạn Minh Đức là chủ một vườn cây ăn quả lớn ở miền Nam. Nếu nhìn từ trên cao xuống, các gốc cây giống như các điểm trên mặt phẳng tọa độ là mặt đất. Đã nhiều năm rồi, bạn Minh Đức không được bội thu do nạn đạo tặc. Do vậy, năm ngoái bạn Minh Đức quyết tâm rào khu vườn của mình lại. Để làm được điều này, bạn Minh Đức chăng đường rào theo các gốc cây để tạo thành một đa giác bao kín vườn cây. Do tính keo kiệt và chi phí của đường rào là rất đắt, bạn Minh Đức đã tính toán chi li để đường rào có chu vi nhỏ nhất có thể. Chắc các bạn cũng biết đây là bài toán tin cơ bản: tìm bao lồi nhỏ nhất của một tập điểm. Tuy nhiên, năm nay bạn Minh Đức cũng không thu hoạch được thêm nhiều. Lý do là có một số cây ở đường biên của hàng rào vẫn không thoát khỏi bàn tay của đạo tặc. Năm nay bạn Minh Đức quyết xây dựng lại hàng rào để cho không còn cây nào nằm ở đường biên nữa. Để làm được điều này, thay vì chăng đường rào theo các gốc cây, bạn Minh Đức sẽ chăng đường rào theo các cột sắt có sẵn trong vườn. Vị trí của các cây và cột sắt đã rõ, nhưng xây dựng làm sao để hàng rào có chu vi nhỏ nhất vẫn là vấn đề nan giải. Bạn hãy giúp bạn Minh Đức giải quyết bài toán khó trên và cùng chia sẻ một vụ mùa bội thu.

Input

Dòng đầu là số ~N~ ~(N \le 100)~. Là số cây trong vườn.

~N~ dòng sau, mỗi dòng ghi ~2~ số là tọa độ của một cây trong vườn.

Dòng tiếp theo là số ~M~ ~(M \le 100)~. Là số cột sắt trong vườn.

~M~ dòng sau, mỗi dòng ghi ~2~ số là tọa độ của một cột sắt.

Các tọa độ đều là số nguyên trong khoảng ~-10000 \dots 10000~.

Output

In ra một số duy nhất là độ dài nhỏ nhất của hàng rào với đúng ~2~ chữ số sau dấu chấm thập phân (có làm tròn). Dữ liệu luôn đảm bảo có ít nhất ~1~ cách xây hàng rào thỏa mãn.

Sample Input

1
0 2
3
-2 0
2 0
0 4

Sample Output

12.94

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.