Runda 15 [Basic] - Krokodyl

14.03.2011 - Damian Rusak
Trudność

 

Zadanie tygodnia

runda 15; kategoria Basic

Limit czasowy: 1s; Limit pamięciowy: 32MB


Krokodyl

W dalekiej krainie krokodyl urządza sobie polowania na zwierzynę pijącą wodę przy brzegach wielkiej rzeki. Krokodyl upatrzył sobie pewien odcinek tej rzeki i na nim zamierza obrać miejsce swego pobytu. Lata doświadczenia dostarczyły mu obserwacji na temat pozycji, które zwierzęta zajmują przy brzegach. Zastanawia się on, gdzie umiejscowić się w rzece, aby suma kwadratów jego odległości do zwierząt była minimalna możliwa - a co za tym idzie - aby miał jak największą szansę schwytania któregoś z nich.

Możemy wyobrażać sobie rzekę na płaszczyźnie jako oś OX. Krokodyl (w związku z odpowiednimi warunkami dla jego bytowania) może umiejscowić się na dowolnym punkcie z zadanego odcinka $ [a,b] $. Zwierzęta reprezentowane są przez punkty na płaszczyźnie. Jako dobra przyjaciółka/przyjaciel krokodyla chcesz mu pomóc i napisać program, który podpowie bestii, który punkt najlepiej nadaje się na jego leże.

Wejście:

Pierwsza linia wejścia zawiera dwie liczby $ a $ i $ b $ ($ -10^{6} \leq a \leq b \leq 10^6 $) - początek i koniec odcinka, na którym może umiejscowić się krokodyl. W kolejnej linii znajduje się jedna liczba $ n $ - liczba zwierząt. ($ 1 \leq n \leq 10^6 $) W kolejnych $ n $ liniach (dla $ i = 1,2,...,n $) znajdują się pary liczb całkowitych $ x_{i} $ $ y_{i} $ - są to współrzędne punktu reprezentującego $ i $-te zwierzę.

Wyjście:

Wyjście powinno zawierać jedną liczbę rzeczywistą $ c $, zaokrągloną do drugiego miejsca po przecinku - współrzędną $ x $ (z przedziału $ [a,b] $) taką, że spośród wszystkich możliwych punktów z tego przedziału, punkt $ (c,0) $ ma najmniejszą sumę kwadratów odległości od punktów reprezentujących zwierzęta.

Przykład 1:

Wejście:

3 5
2
4 6
4 -7

Wyjście:

4.00

 

Przykład 2:

Wejście:

2 7
2
1 6
-3 -7

Wyjście:

2.00

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzasKrokodyl
1Wojtek Nadara1001:54:0110
2Damian Straszak1002:04:0010
3Wojciech Szałapski1033:16:2310
4Przemysław Derengowski1067:20:0010
5Adam Szeptycki1079:30:1410
6Michał Glapa10103:05:3910
7Piotr Bejda10106:40:4810
8Michał Zezyk10150:24:3110
9Witold Długosz10173:59:1510
10Arek Wróbel10181:37:1810
11Paweł Kubik10256:29:2910
12Michal Filipczak10267:18:0510
13Krzysztof Kiljan10278:57:4010
14Adrian Jaskółka10859:13:4610
15Jakub Kaliński937:30:179
16Krzysztof Drab960:51:149
17Krzysztof Cirocki4101:12:114
18Kamil Dębowski309:49:473
19Mateusz Wasylkiewicz1180:33:411
20Paweł Szczur1231:40:021
5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com