Решение задачи 25.
Отсортировав координаты точек в порядке неубывания Х-овых координат, а в случае одинаковых Х-овых координат в порядке неубывания У-овых координат, находим координаты средней точки (находящуюся в позиции n div 2+1), пусть это точка (Х0,У0). При этом множество точек оказалось разбито на 3 части: точки, лежащие на прямой х=Х0; точки, лежащие левее прямой х=Х0; точки, лежащие правее прямой х=Х0. Представим, что точки, лежащие левее прямой х=Х0 ( точки, лежащие правее прямой х=Х0) лежат в пределах некоторого прямоугольника, где Х1 (Х2) координаты его правого (левого) края. Тогда легко понять, что существует прямая с достаточно большим углом наклона, которая разделяет эти части. Осталось разделить только точки на прямой, чтобы количество точек в получившихся частях было соответствующим (т.е. пересечение прямой с прямой х=Х0). Если количество точек нечетно, то искомая линия проходит через среднюю точку, иначе над средней точкой (но под предыдущей, если она лежит па прямой х=Х0).
Определим:
Х1 - может быть легко найдена просмотром массива Х-овых координат справа налево от средней точки до нахождения первой координаты, отличной от Х0. Если такая координата не найдена, то Х1=Х0-1.
Х2 - может быть легко найдена просмотром массива Х-овых координат слева направо от средней точки до нахождения первой координаты, отличной от Х0. Если такая координата не найдена, то Х1=Х0+1.
У1 - это У-овая координата точки, предшествующей средней точке, если Х-ая ее координата равна Х0, или равна У0-1, если Х-овая координата точки, предшествующей средней точке, не равна Х0.
После того, как Х0,У0,Х1,У1 найдены, осталось написать уравнение прямой через точки с координатами (Х2,У2) (Х3,У3), определяемыми по следующему правилу:
если N - четно
то Х2=Х0; У2=(У0+У1)/2, Х3=Х0+Z/2,У3=У0-Ymax+Ymin
иначе Х2=Х0; У2=У0, Х3=Х0+Z/2,У3=У0-Ymax+Ymin
где Ymax- максимальная У-овая координата, Ymin - минимальная У-овая координата, Z=min(Х0-Х1,Х2-Х0).
|
