Runda 4: Powódź

27.10.2009 - Przemysław Uznański
TrudnośćTrudność

Limit czasowy: 14 sekund
Limit pamięciowy: 32 MB

Paweł i Jakub poszli na spacer na łąkę, która leży nieodpodal rzeczki. Łąka ma kształt kwadratu NxN. Niestety rzeczka zaczeła zalewać łąkę. Chłopcy postanowili uciec z łąki, czyli wydostać się poza dowolną boczną krawędź. Ale chcą to zrobić jak najmniejszym wysiłkiem — ustalają zatem prędkość z jaką będą uciekać i chcą by ta prędkość była najmniejsza możliwa. Gdy ustalą prędkość to już cały czas będą poruszać się z tą prędkością.

 

Każdy kwadracik 1x1 łąki ma przypisaną wysokość w metrach nad poziomem rzeki, która oznacza też za ile sekund pole to zostanie zalane. Oczywiście, gdy pole zostanie zalane, wtedy nie będzie można przez nie przejść.

 

Chłopcy mogą przechodzić tylko na te pola, które sąsiadują krawędzią z polem na którym obecnie się znajdują. Idąc z pola do pola, zawsze idziemy od środka jednego pola do środka drugiego po odcinku łączącym oba środki. Odległość ze środka pola do boku pola ma długość pół metra. Przez cały czas przechodzenia przez pole nie może być ono zalane. Woda podnosi się w sposób ciągły.

 

Pomóż Pawłowi i Jakubowi! Napisz program, który wyliczy najmniejszą możliwą predkość, która pozwala na ucieczkę z łąki.

 

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita N (1<=N<=1000), oznaczająca rozmiar łąki. W drugiej linii wejścia są dwie liczby całkowite x, y (1<=x,y<=N), oznaczające współrzędne kwadratu na środku którego Paweł i Jakub znajdują na początku. W N kolejnych liniach znajduje się po N liczb, oznaczające wysokości pól, w i-tej linii j-ta liczba oznacza hji - wysokość pola o współrzędnych (j,i) (1<=hji<=1000). Wysokości pól to liczby zmiennoprzecinkowe podane z dokładnością do maksymalnie 3 cyfr po przecinku.

 

Wyjście

W pierwszej i jedynej linii należy wypisać jedną wartość — minimalna prędkość, w metrach na sekundę, z jaką mogą uciec z łąki, z dokładnością do 3 liczb po przecinku.

 

Przykład

Dla danych wejściowych:

 

3
2 2
2.0 2.0 2.0
2.0 1.0 3.0
3.0 2.0 3.0

poprawną odpowiedzią jest:

 

0.500

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com