Тем, кто дружит с математикой

Рассмотрим все горизонтальные прямые. Среди них либо найдется искомая, либо такая, что 1) Выше неё лежат 1000000 - k точек; 3) На ней лежит k+n точек, 3)) Ниже неё лежат 1000000 - n точек

Выберем на этой прямой точку, лежащую между k-й и k+1-й из отмеченных и повернем прямую на угол х против часовой стрелки. Из непрерывности очевидно, что при достаточно малом х повернутая кривая не пересекает ни одну из отмеченных точек и ни одну не пересекла в процессе поворота. Это и есть искомая прямая

Допустим на плоскости N точек, где N=1 000 000. Если каждую из точек соединить к каждой получится не более чем N*(N+1)/2 прямых (часть прямых могут оказаться параллельными, поэтому не более) . В декартовой плоскости координат конечное множество прямых дает счетное (конечное) множество углов наклона. Выбираем прямую наклон которой не входит в это множество и начинаем придвигать ее с бесконечности. В начальном положении N точек с одной стороны, 0 с другой. Когда прямая надвигается на определенную точку, что счетчик с одной стороны увеличивается, а с другой уменьшается. В определенном положении множество будет поделено пополам.

Наверное так (на большее меня не хватает) .
Выберем точку следующим образом: через нее можно провести прямую так. что все остальные точки лежат в одной полуплоскости - это сделать всегда можно. Из нее проведем лучи через все остальные точки. Предположим общий случай - когда выбранная точка и люые две других не лежат на одной прямой. В этом случае получается 1999999 лучей. Далее проведем через эту точку прямую так, что все остальные точки будут в одной полуплоскости. Перенумеруем лучи начиная с самого ближнего к прямой - и далее. Дальше через выбранную точку проведем еще один луч, так чтобы он проходил между 999999 и 1000000 лучом. Далее, найдем точку, которая находится на самом близком расстоянии от выбранной. Назовем отрезок между выбранной точкой и найденной А. На проведенном луче отметим произвольную точку. Проведем черезнее прямую парал. А. В обе стороны от этой точки отложим отрезки равные А. Получится отрезок длинной 2А. Теперь, осуществим парал. перенос этого отрезка до тех пор, пока он не перестанет пересекать соседние лучи. ВСЁ! Теперь если мы на А и на 2А выберем по произвольной точке и проведем через них прямую - она и будет искомая.
Этому решению надо придать строгий вид - пока это только подробная идея (я так думаю! )
Если расположение точек отлично от нашего произвольного случая, то решение там мгновенно упрощается.