Подсчитать количество точек пересечения прямых

[Jenyyy]

Задано множество прямых на плоскости(коэффициентами своих уравнений). Подсчитать кол-во точек пересечения этих прямых

[Bugrimov]

Выкладывайте наработки, посмотрим.

[Poma][a]

Сканирующая прямая в помощь

[Аватар]

Сообщение от Poma][a

Сканирующая прямая в помощь

Думаешь можно приспособить? Сомневаюсь. Все таки множество прямых, а не отрезков

[Poma][a]

Вот интересное кино.. Нигде не увидел что появился новый ответ.
Приспособить точно можно. Завтра напишу как..
Пардон за столь информативный пост

[Poma][a]

Можно так :
Загнать все в массив структур с полями : угловой и свободный член.
Потом сортируем его по угловому коэфф.
Дальше говорим, что в переменной ans будет ответ. и присваиваем ему n*n
Затем бежим по массиву и считаем кол-во элементов с одинаковым угловым. Как только он становится уже неодинаковым, вычитаем из ans k*(k-1) (где k - кол-во с одинак)

Вот и все

Можно еще придумать тоже самое с ассоциативным массивом (в среднем случае память будем экономить).. Но сложность останется такой же

[ViktorR]

А что Вы скажете по такому случаю, когда, например, у трёх прямых только одна точка пересечения?
Даже у n прямых может быть одна общая точка пересечения ...


Как-то так, ...

[Poma][a]

А мы скажем, что точек 134, но они совпадают

[Аватар]

Ага, общая точка, совпадение прямых да и n*n чет не то - f(k+1)=f(k)+k; f(1)=0

А мы скажем

а нам не поверят

[ViktorR]

Учитывая, что координаты пересечений не целые числа, получаем ещё одну проблему - точность, с которой мы можем сравнивать координаты точек пересечения. При этом придётся вычислять расстояние между точками пересечения: eps - как допустимый радиус, определяющий окрестность точки, в которой все точки пересечения будут совпадать.
Т.о.
- формирование списка, задающего уравнения прямых: a и b;
- тупой перебор систем двух линейных уравнений. Благо, что в одном направлении;
- формирование списка координат точек пересечения. При этом список просматриваем на предмет совпадения координат с заданной точностью. Если нет совпадения, то координаты добавить в список, а иначе - продолжить вычисления. Координаты можно не упорядочивать, и вставлять в голову вместе с подсчитанным числом пересечений;
- вывести подсчитанное число пересечений.


Как-то так, ...