Bảo vệ phòng trưng bày
Đề bài
Mô tả
Phòng trưng bày nghệ thuật ở địa phương bạn sắp tổ chức một triển lãm mới đầy hấp dẫn, trưng bày các tác phẩm điêu khắc của những nghệ sĩ nổi tiếng thế giới, và phòng trưng bày dự kiến sẽ thu hút hàng nghìn khách tham quan. Thật không may, triển lãm cũng có thể thu hút những vị khách không mời mà đến, cụ thể là những tên trộm muốn đánh cắp các tác phẩm nghệ thuật. Trước đây, ban giám đốc phòng trưng bày không mấy bận tâm đến chuyện này, vì bộ sưu tập thường trực của họ, nói thật lòng, không đáng để trộm.
Phòng trưng bày gồm nhiều phòng, và mỗi tác phẩm điêu khắc của triển lãm mới sẽ được đặt ở một phòng khác nhau. Mỗi phòng có một nhân viên bảo vệ và một chuông báo động để giám sát tác phẩm. Khi chuông báo động reo, người bảo vệ sẽ chạy (không rời khỏi phòng) từ vị trí trực của mình tới một vị trí mà từ đó có thể nhìn thấy trực tiếp tác phẩm điêu khắc. Việc này nhằm kiểm tra xem tác phẩm có thực sự bị trộm hay đây lại là một lần báo động nhầm.
Để quyết định nên bố trí người bảo vệ ở đâu cho tốt nhất, ban giám đốc muốn biết người bảo vệ cần bao lâu để nhìn thấy một tác phẩm cho trước. Họ hy vọng bạn có thể giúp!
Mỗi phòng nằm trên một tầng duy nhất, và các bức tường của phòng có thể xấp xỉ bằng một đa giác đơn. Vị trí của người bảo vệ và vị trí của tác phẩm điêu khắc là hai điểm phân biệt nằm hoàn toàn bên trong đa giác (không nằm trên biên). Tác phẩm điêu khắc có dạng hình tròn với bán kính nhỏ không đáng kể (nhưng dương). Để xác nhận tác phẩm vẫn còn đó, người bảo vệ cần nhìn thấy được ít nhất một nửa tác phẩm.
Hình dưới minh họa hai ví dụ của đề. Trong mỗi trường hợp, người bảo vệ xuất phát ở ô vuông màu xanh dương bên trái, và tác phẩm điêu khắc nằm ở hình tròn màu đỏ bên phải. Đường chấm màu xanh dương là đường đi tối ưu của người bảo vệ. Khi người bảo vệ tới vị trí được đánh dấu bằng hình thoi màu xanh lá, anh ta nhìn thấy được một nửa tác phẩm.

Dữ liệu vào
Dòng đầu tiên chứa số nguyên (), số đỉnh của đa giác mô tả căn phòng. Tiếp theo là dòng, mỗi dòng chứa hai số nguyên và () là tọa độ các đỉnh của đa giác theo thứ tự ngược chiều kim đồng hồ.
Dòng tiếp theo chứa hai số nguyên và là vị trí của người bảo vệ. Dòng cuối cùng chứa hai số nguyên và là vị trí tâm của tác phẩm điêu khắc.
Đa giác là đa giác đơn, tức là các đỉnh của nó đôi một phân biệt và không có hai cạnh nào của đa giác cắt nhau hay chạm nhau, ngoại trừ hai cạnh liên tiếp chạm nhau tại đỉnh chung. Ngoài ra, không có hai cạnh liên tiếp nào thẳng hàng.
Dữ liệu ra
In ra quãng đường nhỏ nhất mà người bảo vệ phải di chuyển để có thể nhìn thấy ít nhất một nửa tác phẩm điêu khắc. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không quá .
Ràng buộc
- .
- , tất cả là số nguyên.
- Các đỉnh được cho theo thứ tự ngược chiều kim đồng hồ; đa giác là đa giác đơn và không có hai cạnh liên tiếp thẳng hàng.
- Người bảo vệ và tác phẩm điêu khắc là hai điểm phân biệt nằm hoàn toàn bên trong đa giác.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 8 0 0 20 0 20 30 60 30 60 0 80 0 80 50 0 50 10 10 70 10 |
58.137767414994535 | Hình bên trái. Người bảo vệ đi từ tới góc tường , rồi đi vuông góc tới đường thẳng nối tác phẩm với góc tường . Tổng quãng đường là . |
| 11 0 0 4 0 4 1 5 1 5 0 7 0 7 2 3 2 3 1 2 2 0 2 1 1 6 1 |
2.0 | Hình bên phải. Từ vị trí ban đầu , tia nhìn tới tác phẩm chạm tường phía trên tại đỉnh và chạm tường phía dưới dọc cạnh từ tới , nên cả hai nửa tác phẩm đều bị che. Người bảo vệ đi tới đỉnh : khi đó tường chỉ che phía dưới tia nhìn, nên nhìn thấy được nửa trên của tác phẩm. |
Bình luận