Mảnh bản đồ
Đề bài
Mô tả
Xuất bản bản đồ không phải là việc dễ dàng. Trước hết cần một phép biến đổi phù hợp để thể hiện hình cầu của Trái Đất trên mặt phẳng hai chiều. Sau đó lại nảy sinh một vấn đề khác: phần lớn các bản đồ chất lượng cao quá lớn để in trên một trang giấy. Để giải quyết, các nhà xuất bản bản đồ thường chia bản đồ thành nhiều mảnh hình chữ nhật và in mỗi mảnh trên một trang. Trong bài này, bạn sẽ khảo sát quá trình "chia mảnh" đó.
Công ty Xuất bản Bản đồ Quốc tế (ICPC) cần cắt giảm chi phí in ấn bằng cách giảm tối đa số mảnh dùng cho mỗi bản đồ. Ngay cả khi kích thước mảnh (do khổ giấy quyết định) và tỉ lệ bản đồ đã cố định, bạn vẫn có thể cải thiện bằng cách dịch chuyển lưới mảnh.
Hình bên trái dưới đây có mảnh bản đồ phủ một vùng. Hình bên phải cho thấy có thể phủ cùng vùng đó chỉ bằng mảnh mà không thay đổi kích thước hay hướng của các mảnh.

Nhiệm vụ của bạn là giúp ICPC tìm số mảnh ít nhất cần dùng để phủ một vùng cho trước. Để đơn giản, vùng được cho dưới dạng một đa giác kín không tự cắt.
Các mảnh phải thuộc một lưới hình chữ nhật song song với trục và trục : chúng chỉ tiếp xúc nhau theo nguyên cả cạnh và không được xoay. Mọi mảnh có kích thước ( theo trục , theo trục ). Lưu ý rằng dù mọi tọa độ trong dữ liệu vào đều là số nguyên, các mảnh có thể nằm ở tọa độ không nguyên.
Đa giác được phép chạm vào các đường biên của mảnh (như ở ví dụ thứ hai). Tuy nhiên, để tránh vấn đề về số thực, bạn có thể giả sử rằng đáp án tối ưu không thay đổi ngay cả khi đa giác được phép ló ra ngoài các mảnh một khoảng .
Dữ liệu vào
Dữ liệu gồm một test duy nhất:
- Dòng đầu chứa ba số nguyên , và : số đỉnh của đa giác và kích thước của mỗi mảnh.
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và : tọa độ một đỉnh của đa giác biểu diễn vùng cần phủ. Các đỉnh được liệt kê theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.
Dữ liệu ra
In ra số mảnh ít nhất cần dùng để phủ toàn bộ phần trong của đa giác.
Ràng buộc
- .
- .
- , .
- Đa giác không tự cắt.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 12 9 9 1 8 1 16 6 16 9 29 19 31 23 24 30 23 29 18 20 12 22 8 14 0 14 8 |
10 | Mảnh có kích thước ; đặt lưới hợp lý thì mảnh là đủ. |
| 4 5 7 10 10 15 10 15 17 10 17 |
1 | Đa giác là hình chữ nhật , đúng bằng một mảnh: đặt lưới sao cho đường lưới trùng với các cạnh của nó thì chỉ cần mảnh (đa giác chỉ chạm biên của các mảnh xung quanh nên không tính các mảnh đó). |
Bình luận