RAOVUON - Rào Vườn
Giới hạn- Thời gian: 0.134s
- Bộ nhớ: 1536MB
- Mã nguồn: 10000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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 <= 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 <= 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..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.
Example
Input: 1 0 2 3 -2 0 2 0 0 4 Output: 12.94
- Người up: beo_map
- Nguồn bài: (none)