Phục vụ phòng
Đề bài
Mô tả
Bạn đang làm việc cho một công ty thiết kế những chú robot hút bụi dễ thương và vui nhộn. Ở mức tổng quát, hành vi của robot được chia thành ba chế độ:
- Khám phá
- Hút bụi
- Tàn sát không kiểm soát
Đáng tiếc là trong khi thử nghiệm với người tiêu dùng cho thấy hai chế độ sau hoạt động hoàn hảo, chế độ khám phá vẫn còn lỗi. Bạn được giao nhiệm vụ gỡ lỗi.
Khi bắt đầu chế độ khám phá, robot được đặt vào một căn phòng có dạng đa giác lồi. Robot có cảm biến cho biết vị trí của mọi bức tường. Công việc của bạn là viết chương trình kiểm tra các số đo này có đúng hay không. Để làm vậy, robot cần chạm vật lý vào mọi bức tường trong phòng.
Bài toán của bạn như sau: cho hình dạng của một căn phòng đa giác lồi có bức tường (mỗi bức tường là một cạnh của đa giác) và một điểm xuất phát nằm bên trong phòng, hãy tìm độ dài của lộ trình ngắn nhất xuất phát từ , chạm vào mọi bức tường rồi quay trở về . Chạm vào một góc phòng (một đỉnh của đa giác) được tính là chạm vào cả hai bức tường kề với góc đó.
Dữ liệu vào
Dữ liệu gồm nhiều bộ test, đọc tới hết file. Mỗi bộ test bắt đầu bằng một dòng chứa số đỉnh của đa giác () và hai số nguyên , là tọa độ điểm xuất phát của robot (). Tiếp theo là dòng, mỗi dòng chứa hai số nguyên , () là tọa độ một đỉnh của đa giác.
Các đỉnh được cho theo thứ tự ngược chiều kim đồng hồ, mọi góc trong đều nhỏ hơn độ, đa giác không tự cắt, và điểm xuất phát của robot nằm hẳn bên trong đa giác.
Dữ liệu ra
Với mỗi bộ test, in số thứ tự bộ test và độ dài của lộ trình cần tìm theo dạng Case i: L (bộ test đánh số từ ). Độ dài cần chính xác tới hai chữ số sau dấu chấm thập phân (đáp án được chấp nhận nếu sai lệch không quá so với đáp án của ban giám khảo).
Ràng buộc
- .
- , mọi tọa độ là số nguyên.
- Đa giác lồi ngặt, đỉnh cho theo thứ tự ngược chiều kim đồng hồ; nằm hẳn bên trong đa giác.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 0 0 -1 -1 1 -1 1 1 -1 1 3 10 1 0 0 30 0 0 20 |
Case 1: 5.66 Case 2: 36.73 |
Bộ 1: phòng hình vuông cạnh , robot ở tâm; lộ trình ngắn nhất là hình thoi nối trung điểm bốn cạnh, dài . Bộ 2: phòng tam giác vuông, lộ trình ngắn nhất dài khoảng . |
| 3 1 1 40 0 0 30 0 0 |
Case 1: 48.00 | Phòng tam giác vuông với các đỉnh , , , robot ở . Lộ trình ngắn nhất lần lượt chạm ba bức tường (mỗi lần chạm, góc tới bằng góc phản xạ), dài khoảng , làm tròn thành . |
Bình luận