Khuôn thép

Để chuẩn bị cho Lễ hội kỷ niệm $30$ năm ngày Chiến dịch Hồ Chí Minh toàn thắng, giải phóng miền Nam, thống nhất đất nước, người ta cần gia công các loại khuôn thép có hình dạng là các hình đa giác lồi $M$ đỉnh. Mỗi khuôn thép được thiết kế trên một tấm thép cũng có hình dạng là một hình đa giác lồi $N$ đỉnh, không có cạnh nào của khuôn thép nằm gọn trên một cạnh của tấm thép. Để tiện cho việc gia công, khuôn thép được vẽ sao cho hai đường thẳng chứa hai cạnh không kề nhau của nó không cắt nhau ở bên trong tấm thép.

Công việc chính cần làm trong quá trình gia công là sử dụng máy cắt để cắt được khuôn thép từ tấm thép ra. Rõ ràng là cần phải thực hiện $M$ nhát cắt. Mỗi nhát cắt được thực hiện bằng cách chọn một cạnh nào đó của khuôn thép và cắt theo đường thẳng chứa cạnh ấy chia tấm thép (phần còn lại sau các nhát cắt trước) thành hai phần, giữ lại phần chứa khuôn thép cần gia công. Chi phí cắt khuôn thép là tổng chiều dài của các đường cắt.

Ví dụ, với tấm thép là tứ giác có các đỉnh $(2,1)$, $(2,5)$, $(5,3.5)$, $(5,2)$ và khuôn thép là hình vuông có các đỉnh $(3,3)$, $(3,4)$, $(4,4)$, $(4,3)$, có thể cắt lần lượt theo các đường thẳng $y=3$ (đường cắt dài $3$), $x=3$ (dài $1.5$), $y=4$ (dài $1$) và $x=4$ (dài $1$), với tổng chi phí bằng $6.5$ đơn vị.

Yêu cầu: Cho biết hình dạng tấm thép và khuôn thép cần gia công. Hãy tìm phương án cắt khuôn thép có chi phí nhỏ nhất.

Dữ liệu vào

• Dòng đầu ghi số $N$ là số đỉnh của tấm thép.
• $N$ dòng tiếp theo, mỗi dòng ghi $2$ số thực $x$ và $y$, là toạ độ $N$ đỉnh của tấm thép được liệt kê theo chiều kim đồng hồ bắt đầu từ một đỉnh nào đó.
• Dòng tiếp theo ghi số $M$ là số đỉnh của khuôn thép.
• Cuối cùng là $M$ dòng, mỗi dòng ghi $2$ số thực $x$ và $y$ là toạ độ $M$ đỉnh của khuôn thép được liệt kê theo chiều kim đồng hồ bắt đầu từ một đỉnh nào đó.

Các số trên một dòng cách nhau ít nhất một dấu cách.

Dữ liệu ra

In ra một số thực duy nhất là chi phí nhỏ nhất tìm được, với $4$ chữ số sau dấu chấm thập phân. Kết quả được chấp nhận nếu sai khác so với đáp án không quá ${10}^{-3}$.

Ràng buộc

• $3\le N\le 2000$, $3\le M\le 2000$.
• $-{10}^4<x,y<{10}^4$; các toạ độ có không quá $4$ chữ số sau dấu chấm thập phân.
• Khuôn thép nằm trong tấm thép; hai đa giác đều lồi (không có ba đỉnh liên tiếp thẳng hàng).

Ví dụ