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

РМ>>Если такого из наших двух нет, то значит нет вообще.
К>Неправда. Контрпример: два круга, один вписан в квадрат, а другой — в угол квадрата.
К>По обоим проекциям будет вложение, хотя очевидно, что через точку касания проходит разделительная прямая.
Ой.
Могу предложить тогда взять не два, а три направления под углами 60 градусов. Вроде должно помочь.

К>Вот на этих вращениях ты и получишь искомый N*logN, если не больше.
Неа. N — число точек. Единственная операция, зависящая от N, вычисление проекций. А она повторяется независимое от кол-ва точек раз. Так что O(N). Ведь O( 100000000 * N ) == O( N ) В чем и заключался основной смысл, остальное так, догадки. Можно еще что-нибудь придумать на базе этого.

Другой вариант: нарисовать эти точки с достаточным разрешением ( как бы только это достаточное разрешение за O(N) выяснить ) и работать далее с рисунком. То же можно что-нибудь выдумать.