![]() |
|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
|
Опции темы | Поиск в этой теме |
![]() |
#1 |
Регистрация: 11.10.2014
Сообщений: 3
|
![]()
Задано множество прямых на плоскости(коэффициентами своих уравнений). Подсчитать кол-во точек пересечения этих прямых
|
![]() |
![]() |
![]() |
#2 |
C/C++, Java
Участник клуба
Регистрация: 28.03.2012
Сообщений: 1,680
|
![]()
Выкладывайте наработки, посмотрим.
![]()
"Keep it simple" - придерживайтесь простоты!
Уильям Оккам - "Не следует множить сущее без необходимости" Сложность - враг простоты и удобства! |
![]() |
![]() |
![]() |
#3 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]()
Сканирующая прямая в помощь
|
![]() |
![]() |
![]() |
#4 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
![]()
Думаешь можно приспособить? Сомневаюсь. Все таки множество прямых, а не отрезков
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
![]() |
![]() |
![]() |
#5 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]()
Вот интересное кино.. Нигде не увидел что появился новый ответ.
Приспособить точно можно. Завтра напишу как.. Пардон за столь информативный пост |
![]() |
![]() |
![]() |
#6 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]()
Можно так :
Загнать все в массив структур с полями : угловой и свободный член. Потом сортируем его по угловому коэфф. Дальше говорим, что в переменной ans будет ответ. и присваиваем ему n*n Затем бежим по массиву и считаем кол-во элементов с одинаковым угловым. Как только он становится уже неодинаковым, вычитаем из ans k*(k-1) (где k - кол-во с одинак) Вот и все Можно еще придумать тоже самое с ассоциативным массивом (в среднем случае память будем экономить).. Но сложность останется такой же |
![]() |
![]() |
![]() |
#7 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,382
|
![]()
А что Вы скажете по такому случаю, когда, например, у трёх прямых только одна точка пересечения?
Даже у n прямых может быть одна общая точка пересечения ... Как-то так, ...
Как-то так, ...
|
![]() |
![]() |
![]() |
#8 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]()
А мы скажем, что точек 134, но они совпадают
|
![]() |
![]() |
![]() |
#9 | |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
![]()
Ага, общая точка, совпадение прямых да и n*n чет не то - f(k+1)=f(k)+k; f(1)=0
Цитата:
![]()
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 25.05.2015 в 11:08. |
|
![]() |
![]() |
![]() |
#10 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,382
|
![]()
Учитывая, что координаты пересечений не целые числа, получаем ещё одну проблему - точность, с которой мы можем сравнивать координаты точек пересечения. При этом придётся вычислять расстояние между точками пересечения: eps - как допустимый радиус, определяющий окрестность точки, в которой все точки пересечения будут совпадать.
Т.о. - формирование списка, задающего уравнения прямых: a и b; - тупой перебор систем двух линейных уравнений. Благо, что в одном направлении; - формирование списка координат точек пересечения. При этом список просматриваем на предмет совпадения координат с заданной точностью. Если нет совпадения, то координаты добавить в список, а иначе - продолжить вычисления. Координаты можно не упорядочивать, и вставлять в голову вместе с подсчитанным числом пересечений; - вывести подсчитанное число пересечений. Как-то так, ...
Как-то так, ...
|
![]() |
![]() |
![]() |
|
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Задано множество прямых на плоскости (коэффициентами своих уравнений). Подсчитать количество точек пересечения этих прямых | клепэ | C# (си шарп) | 3 | 03.11.2013 23:37 |
Вычисление количества различных точек пересечения двух прямых | x3Braid | Помощь студентам | 1 | 11.06.2012 17:18 |
Подсчитать количество равносторонних треугольников с вершинами в заданном множестве точек на плоскости (Delphi) | dea_celeste | Помощь студентам | 4 | 17.05.2012 15:33 |
Точки пересечения прямых | Вернер | Помощь студентам | 0 | 11.05.2012 17:38 |
подсчитать количество точек пересечения | fallti | Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM | 3 | 28.06.2010 13:46 |