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

D>Есть два множества точек на плоскости.
D>То есть, можна ли провести прямую, что
D>разделит плоскость на две подплоскости в которых будут лежать эти множества.
То есть, можно ли найти такое направление, что проекции точек на прямую в этом направлении... ( в общем ясно )

D>Главные прикол, что сделать это надо за О(N).
Очевидно, что проекции строятся за O(N).

Далее дело техники. Видимо, не составит труда уже независимо от кол-ва точек ( нас интересуют только по две крайние для каждого множества ) найти такое направление или убедится, что его нет.

Берем два перепендикулярных направления. Выбираем то, для которого проекции множеств выглядят не так: < { } >.
Если такого из наших двух нет, то значит нет вообще.
Если уже получили < > { }, то все готово.
Иначе находим в какую сторону вращать, чтобы уменьшать область перекрытия и вращаем. Можно применять всякие методы Ньютона, касательных, хорд и всех остальных.