Для разнообразия предложу новую задачу.

Пятна. На стене. Будем считать, точечные. N штук. Надо их всех накрыть одной или двумя картинами.
Картины не пересекаются, размеры — любые, но сумма площадей должна быть минимальна.

Найти решение со сложносью <= N*log(N)*const операций.

Здравствуйте, mihoshi, Вы писали:

M>Для разнообразия предложу новую задачу.

M>Пятна. На стене. Будем считать, точечные. N штук. Надо их всех накрыть одной или двумя картинами.
M>Картины не пересекаются, размеры — любые, но сумма площадей должна быть минимальна.

M>Найти решение со сложносью <= N*log(N)*const операций.

А я в отместку скажу, что это классический алгоритм построения R-tree!!!!!!
Которые есть в Oracle, PostgreesSQL, и других...!!!!!!

Здравствуйте, vvaizh, Вы писали:

V>Здравствуйте, mihoshi, Вы писали:

M>>Для разнообразия предложу новую задачу.

M>>Пятна. На стене. Будем считать, точечные. N штук. Надо их всех накрыть одной или двумя картинами.
M>>Картины не пересекаются, размеры — любые, но сумма площадей должна быть минимальна.

M>>Найти решение со сложносью <= N*log(N)*const операций.

V>А я в отместку скажу, что это классический алгоритм построения R-tree!!!!!!
V>Которые есть в Oracle, PostgreesSQL, и других...!!!!!!

? Все ГОРАЗДО проще.

Здравствуйте, mihoshi, Вы писали:

M>Для разнообразия предложу новую задачу.

M>Пятна. На стене. Будем считать, точечные. N штук. Надо их всех накрыть одной или двумя картинами.
M>Картины не пересекаются, размеры — любые, но сумма площадей должна быть минимальна.

M>Найти решение со сложносью <= N*log(N)*const операций.

А они хоть прямоугольные (картины)?

Здравствуйте, mihoshi, Вы писали:

M>Для разнообразия предложу новую задачу.

M>Пятна. На стене. Будем считать, точечные. N штук. Надо их всех накрыть одной или двумя картинами.
M>Картины не пересекаются, размеры — любые, но сумма площадей должна быть минимальна.

А что так — одной или двумя? а остальные картины куда девать, пусть в чулане валяются?
а картины поворачивать можно или нет? И что считать за операцию? сортировка точек по одной из координат — это одна операция или сколько?

Здравствуйте, IPv6, Вы писали:

IP>Здравствуйте, mihoshi, Вы писали:

M>>Для разнообразия предложу новую задачу.

M>>Пятна. На стене. Будем считать, точечные. N штук. Надо их всех накрыть одной или двумя картинами.
M>>Картины не пересекаются, размеры — любые, но сумма площадей должна быть минимальна.

IP>А что так — одной или двумя? а остальные картины куда девать, пусть в чулане валяются?
IP>а картины поворачивать можно или нет? И что считать за операцию? сортировка точек по одной из координат — это одна операция или сколько?

Ах да. Картины прямоугольные. Пишутся на заказ специально для такого случая. Стороны параллельны или перпендикулярны полу.

Операция — одна команда ассемблера.

Сортировка картин по соординате — n * log(n) * const операций.