|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Stanislav Shwartsman 2:400/520 26 May 2001 14:51:32
To : All
Subject : Weighted mediam
--------------------------------------------------------------------------------
Задача попалась такая нехорошая:
Дано N точек на плоскости с координатами Pi(Xi, Yi) и весом Wi каждая.
Hайти сабж для этих точек - такую точку P(X,Y) на плоскости, что для нее
N
Sum [ Wi*D(Pi, P) ] i=1
будет минимальным. D - расстояние между точками, вычисляется по формуле
D(Pi, P) = abs(Xi-X) + abs(Yi-Y)
Сложность алгоритма должна быть O(N), запрещается пользоваться
итеративными математическими выражениями, которые накапливают ошибку
в точности.
Второй день сижу, ничего в голову не приходит ;(
У кого есть идеи ?
E-mail: gate@fidonet.org.il
Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)
Bye !
Stanislav (AKA Night's Man) [Team Technion]
---
* Origin: Gate From Another World ... From Haifa, Israel (2:400/520)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
