Ghép hình đa giác
Đề bài
Mô tả
Trong kỳ ICPC World Finals năm ngoái ở Marrakesh, một giám khảo đã mua một bộ xếp hình bằng gỗ rất đẹp vẽ một con lạc đà và những cây cọ (xem hình thứ nhất). Khác với các bộ xếp hình truyền thống, thường được tạo bằng cách cắt nhỏ một bức tranh hình chữ nhật có sẵn, mọi mảnh của bộ xếp hình này được cắt và sơn riêng. Vì thế, các mảnh kề nhau thường không có chung chi tiết hình vẽ hay màu sắc. Hơn nữa, bản thân bức tranh hoàn chỉnh cũng có hình dạng bất thường. Với những đặc điểm đó, hình dạng của từng mảnh thường là cách duy nhất để biết mỗi mảnh nên đặt ở đâu.

Hình 1: bộ xếp hình bằng gỗ của vị giám khảo.
Từ năm ngoái tới giờ, vị giám khảo vẫn tự hỏi liệu có thể viết một chương trình giải bộ xếp hình này hay không. Một phần quan trọng của chương trình như vậy là cách đánh giá hai mảnh ghép "khớp" với nhau tốt đến mức nào. Hai mảnh khớp càng tốt thì càng có khả năng chúng nằm cạnh nhau trong bức tranh.
Các mảnh được mô hình hóa bằng đa giác đơn. Nhiệm vụ của bạn là tìm một cách đặt hai đa giác đã cho sao cho phần trong của chúng không chồng lên nhau, nhưng hai đa giác chạm nhau bằng biên, và độ dài phần biên chung là lớn nhất. Khi đặt, các đa giác được phép tịnh tiến và quay, nhưng không được lật (lấy đối xứng) hay thay đổi kích thước. Hình 2 minh họa cách đặt tối ưu của ví dụ thứ nhất.

Hình 2: hai đa giác của ví dụ thứ nhất (bên trái) và cách đặt tối ưu của chúng (bên phải), phần biên chung tô màu đỏ.
Dữ liệu vào
Dữ liệu vào gồm mô tả của hai đa giác, lần lượt từng đa giác. Mô tả mỗi đa giác bắt đầu bằng một dòng chứa số nguyên , số đỉnh của đa giác. Tiếp theo là dòng, mỗi dòng chứa hai số nguyên , : tọa độ một đỉnh của đa giác.
Các đỉnh của mỗi đa giác được cho theo chiều kim đồng hồ, và không có ba đỉnh liên tiếp nào thẳng hàng. Dữ liệu được chọn sao cho kể cả khi các đỉnh bị dịch chuyển một khoảng tới , đáp án cũng không tăng quá .
Dữ liệu ra
In ra độ dài lớn nhất có thể của phần biên chung của hai đa giác khi chúng được đặt tối ưu. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối nhỏ hơn .
Ràng buộc
- với mỗi đa giác.
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 8 0 0 0 10 10 10 15 15 24 6 24 10 30 10 30 0 7 -5 0 -5 10 10 10 15 5 20 10 35 10 35 0 |
30.142135624 | Đây là hai đa giác trong hình 2. Quay đa giác thứ nhất và đặt lên trên đa giác thứ hai, mũi nhọn của nó lọt vào rãnh chữ V: phần biên chung gồm hai cạnh của rãnh (mỗi cạnh dài ) và hai đoạn nằm ngang dài và , tổng cộng . |
| 3 1 0 0 30 40 0 3 1 0 0 30 40 0 |
50 | Hai tam giác giống nhau. Quay một tam giác quanh trung điểm cạnh dài nhất (dài ) để hai cạnh này trùng nhau. |
Bình luận