Submit | All submissions | Best solutions | Back to list |
MAJMUN - MAJMUN |
English | Vietnamese |
Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/majmun
Đ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
Added by: | sieunhan |
Date: | 2009-01-23 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO PERL6 |
Resource: | Croatia national contest 2008 |