задача про треугольник, и его медиану.. |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
задача про треугольник, и его медиану.. |
krasnblj |
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 20 Пол: Мужской Репутация: 0 |
для всех задач дано N точек плоскости.Найти три точки среди заданых точек чтобы треугольник с вершинами в этих точках содержал бы наименьшую медиану.
ну хоть малейшие подсказки,сам код не начинал.. хотябы связь.. |
Lapp |
Сообщение
#2
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Ничего в голову не приходит, кроме полного перебора всех треугольников с вычислением всех трех медиан...
Задачу можно сделать более интересной, если постараться избежать повторов. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Michael_Rybak |
Сообщение
#3
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Вообще, конечно, можно тут диаграммы Вороного заюзать. Тогда получится за n^2 * log n. Рассказать?
|
krasnblj |
Сообщение
#4
|
Новичок Группа: Пользователи Сообщений: 20 Пол: Мужской Репутация: 0 |
Michael_Rybak я этого еще не проходил,расскажи ))
|
Michael_Rybak |
Сообщение
#5
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
можно для каждой пары вершин находить середину соединяющего их отрезка, и для этой середины сразу выбирать ближайшую вершину среди остальных (она и будет третьей).
чтобы это делать, нужно сначала построить диаграмму Вороного для этого множества точек. Тогда поиск ближайшей будет всегда происходить за log n. |
krasnblj |
Сообщение
#6
|
Новичок Группа: Пользователи Сообщений: 20 Пол: Мужской Репутация: 0 |
оу,не,решил делать перебором,не знаю как подойти,что за что обозначить и как выводить ответ - корродинаты начал и конца медианы или её длину?? о.О
|
Michael_Rybak |
Сообщение
#7
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Ответом будут сами точки - вершины треугольника. Т.е. ты перебираешь все тройки А, В, С, для каждой тройки находишь три медианы, выбираешь наименьшую, и запоминаешь ту тройку, в которой самая маленькая наименьшая медиана. Можешь кроме треугольника вывести и ее длину.
|
krasnblj |
Сообщение
#8
|
Новичок Группа: Пользователи Сообщений: 20 Пол: Мужской Репутация: 0 |
в ощем написал код,всё работает,но такой тест: количество точек : 5 точки: (1,1) (-1,-1) (0,0) (0.5,0.5) (-0.5,-0.5) выдет три точки на которых лежит треугольник с наименьшей медианой,хотя мы видим что все это точки лежат на одной прямой,следовательно треугольника не существует.. зы: когда мы вводим точки в другом поряд выводит другой ответ,хотя точка "(-0.5,-0.5)" присутствует всегда.. помгие плззззз |
Michael_Rybak |
Сообщение
#9
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
ну добавь проверку, что точки IJK не лежат на одной прямой.
|
krasnblj |
Сообщение
#10
|
Новичок Группа: Пользователи Сообщений: 20 Пол: Мужской Репутация: 0 |
так если 2 точки лежат на одной прямой,а третья где-то в стороне,то тогда тругольник может существовать!!
|
Michael_Rybak |
Сообщение
#11
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
проверяй что все три не лежат. любые две всегда лежат
|
krasnblj |
Сообщение
#12
|
Новичок Группа: Пользователи Сообщений: 20 Пол: Мужской Репутация: 0 |
хм,не предтваляю как это написать..
|
Michael_Rybak |
Сообщение
#13
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Точки А В С лежат на одной прямой если (AX-BX)(CY-BY) = (CX-BX)(AY-BY)
|
krasnblj |
Сообщение
#14
|
Новичок Группа: Пользователи Сообщений: 20 Пол: Мужской Репутация: 0 |
спс,но мне другой способ подсказали,ищу как его внедрить )))
|
krasnblj |
Сообщение
#15
|
Новичок Группа: Пользователи Сообщений: 20 Пол: Мужской Репутация: 0 |
ну поччеееееемууууу он всегда MQ выводит равный нулю???? |
Michael_Rybak |
Сообщение
#16
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Потому что нужно не m[3]:=mq; а mq:=m[3];
|
krasnblj |
Сообщение
#17
|
Новичок Группа: Пользователи Сообщений: 20 Пол: Мужской Репутация: 0 |
щёрт,точно,ты и не представляешь как я тебя абажаю )))))))))
|
Michael_Rybak |
Сообщение
#18
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
|
Текстовая версия | 27.04.2024 8:25 |