<ПРЕД Задача:
СЛЕД>
Задачу решили 290 пользователей: ...
UserDateAttemptTimeCMSC
abortmozga.ru29 mar 2009C++1604.19180 
DAV13 jul 2009C++1700.01183 
DAV22 jun 2009C++1400.01189 
WsemirZ21 jul 2008Kylix3603.69189 
abortmozga.ru29 mar 2009C++1204.19189 
abortmozga.ru29 mar 2009C++1104.13190 
Stranger08 dec 2006FPC504.27190 
DAV22 jun 2009C++1500.01191 
DAV22 jun 2009C++1300.01193 
yf888814 nov 2006FPC204.29194 
Stranger02 oct 2006FPC304.26200 
tomek20 mar 2006C++305.00201 
DAV16 mar 2009C++900.01202 
DmitryLyugaevKantSU20 nov 2007Kylix304.19203 
VArt12 jan 2009C++204.09218 
fetetriste04 aug 2008C++1700.01226 
fetetriste04 aug 2008C++1800.01226 
BobicZdoh16 mar 2006Python113.77228 
fetetriste03 aug 2008C++1600.01229 
Языки
C++
153
FPC
79
Kylix
25
C
19
Java
15
Python
2
Ruby
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Минимальная сумма расстояний

Time limit = 5

Рассмотрим N точек на плоскости XY, заданных своими декартовыми координатами. Назовем эти точки фокусами. У каждого фокуса есть дополнительный параметр f — сила фокуса. Вы должны найти такую точку А(х, у), что сумма fi * D( (xi, yi), (x, y) ) минимальна из всех возможных. fi — сила i-го фокуса, D(P, Q) — это расстояние между точками P и Q, (xi, yi) — координаты i-го фокуса.

Вход В первой строке входных данных содержится одно целое число N, 1 ≤ N ≤ 100. Затем следуют N строчек, каждая из которых состоит из трех чисел: xi, yi, fi, где xi, yi — декартовы координаты i-го фокуса, fi — его мощность. xi и yi — целые числа, -15 ≤ xi, yi ≤ 15, fi — тоже целое, 0 < fi < 20

Выход Ваша программа должна вывести два числа с плавающей точкой — координаты точки А. Числа должны быть записаны с двумя десятичными знаками после запятой. Допустимое отклонение для выходных данных +-1 в последнем знаке.

Вход#1
1
0 0 1

Выход#1
0.00 0.00

Вход#2
2
0 0 2
0 1 1

Выход#2
0.00 0.00

Вход#3
3
0 0 10
0 1 10
1 0 10

Выход#3
0.21 0.21


Автор:
Малых Антон
25 апреля 2003

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 18.207.130.162