MAJMUN - MAJMUN
Giới hạn- Thời gian: 0.136s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Đi từ trường về nhà sau một ngày học căng thẳng, Ivica đã sẵn sàng giải lao bằng trò chơi điện tử "Khỉ & chuối".
Trong trò chơi, chú khỉ ở trong một khu rừng mà trên mỗi điểm có toạ độ nguyên đề có một cái cây và mỗi cái cây đều nằm trên một điểm có toạ độ nguyên. Ban đầu, chú khỉ ở vị trí (Xm, Ym) và hướng mặt về (Xm,Ym +1). Ivica điều khiển chú khỉ bằng các phím 0..7. Khi Ivica ấn phím thứ K, khỉ quay mặt sang trái 45 độ K lần và nhảy đến cái câu đầu tiên mà nó nhìn thấy (sau khi đã quay mặt).
Trò chơi kết thúc sau khi ấn N phím. Sau đó, điểm được tính dựa trên khoảng cách giữa khỉ và cây chuối (khoảng cách Euclide). Khoảng cách càng gần, điểm càng cao. Sau khi kết thúc trò chơi, Ivica muốn biết rằng cậu có thể đạt kết quả như thế nào nếu chỉ thay đổi nhiều nhất một phím. Bạn hãy giải bài toán này.
Input
Dòng 1: gồm 4 số Xm, Ym, Xb, Yb (0<= Xm, Ym, Xb, Yb<=1 000 000) là toạ độ ban đầu của khỉ và toạ độ của cây chuối.
Dòng 2: Gồm số nguyên N (1<=N<=100 000), số lần bấm phím
Dòng 3: Xâu gồm N kí tự trong khoảng '0'.. '7', là các phím mà Ivica đã bấm (theo thứ tự)
Output
Gồm một dòng duy nhất chứa khoảng các mà Ivica có thể đạt được nếu thay đổi nhiều nhất một lần bấm phím. Kết quả của bạn được coi là chính xác nếu sai khác không quá 0.01 so với kết quả của ban tổ chức
Example
Input: 0 0 2 3 5 15102 Output: 0.000000
Input: 5 5 10 5 3 000 Output: 2.000000
Input: 0 0 10 10 9 700003000 Output: 1.414214
- Người up: huy391992
- Nguồn bài: Croatia national contest 2008