De thi tin QT IOI 19912
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (104.75 KB, 1 trang )
<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>
Bai toan 2 - 1991
<b>II. Bài toán rào cây </b>
Một nông dân muốn bảo tồn một loại cây bách cổ quý hiếm. Để làm điều này, ông ta ghi nhớ vị trí
của mỗi cây và quyết định dùng dây kim loại rào quanh cây theo một hình đa giác để cây nằm
tồn bộ trong đó. Để giảm chi phí, ơng ta cần tính chiều dài dây kim loại tối thiểu nhất. Người
nông dân muốn xây một ngơi nhà hình chữ nhật, một trong các cạnh nhà song song với trục X và
ơng ta cần biết vị trí tương đối của ngơi nhà:
(1) Ngơi nhà nằm bên ngồi hàng rào hình đa giác.
(2) Ngơi nhà nằm trong hàng rào hình đa giác.
(3) Hàng rào chia ngơi nhà thành hai phần có diện tích khác 0.
Hãy viết chương trình thực hiện các cơng việc sau:
(A) Tìm các cây nằm ở đỉnh đa giác.
(B) Tính chiều dài của dây kim loại cần sử dụng.
(C) Chỉ ra vị trí của ngơi nhà trong ba trường hợp (1,2,3) trên.
<i><b>Dữ liệu vào: </b></i>
- Dòng đầu tiên là N - số cây (N <= 20).
- N dòng tiếp theo, mỗi dòng là hai số (Xi,Yi), 1 <= i <= N, Xi, Yi > 0 - là tọa độ của cây thứ i.
- Dòng cuối cùng là các số (a,b), (c,d); a, b, c, d > 0 - cho biết toạ độ điểm bắt đầu và kết thúc của
đường chéo ngôi nhà.
<i><b>Kết quả: </b></i>
- Đưa ra một dãy M điểm (1 <= M <= N) với tính chất là nếu ta đi theo các điểm này theo thứ tự
mà chúng xuất hiện, ta sẽ được một hình đa giác ngồi (đa giác gồm M đỉnh là vị trí của M cây và
bao quanh toàn bộ N điểm - vị trí của N cây).
- Chiều dài kim loại cần sử dụng.
- Vị trí ngơi nhà theo dạng "1","2" hoặc "3".
</div>
<!--links-->
