Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Точки и треугольники
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
zener zener вне форума
Member
 
Сообщений: 56
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.10.2010
По умолчанию Точки и треугольники - 10.11.2011, 22:37

Привет.. можете помочь, пожалуйста, с задачкой?

"Задаются точки на плоскости.их число - 3*N (точка задается координатой Х и У, координаты - целые числа).Любые 3 точки не должны лежать на одной прямой.нужно разбить эти точки на N групп точек так, чтобы точки будут являться вершинами треугольника в каждой группе, чтобы суммарная площадь всех треугольников была минимальной."
мне хотя б разобраться, как можно было б разбить эти точки на треугольники((
Ответить с цитированием
  (#2 (permalink)) Старый
aag aag вне форума
ушёл... не вернётся)))
 
Сообщений: 3,400
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
По умолчанию 10.11.2011, 22:58

Цитата:
Сообщение от zener Посмотреть сообщение
...мне хотя б разобраться, как можно было б разбить эти точки на треугольники((
Ну, дёргаем N раз по три точки... С остатком - следующие три точки дёргаются из списка без уже выдернутых. Считаем по трём точкам площадь - сходу не скажу, Сами как-нибудь. И площадь > 0 (реальный треугольник). Складываем эти площади по ходу, сравниваем...
Ответить с цитированием
  (#3 (permalink)) Старый
zener zener вне форума
Member
 
Сообщений: 56
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.10.2010
По умолчанию 10.11.2011, 23:22

Цитата:
Сообщение от aag Посмотреть сообщение
Ну, дёргаем N раз по три точки... С остатком - следующие три точки дёргаются из списка без уже выдернутых. Считаем по трём точкам площадь - сходу не скажу, Сами как-нибудь. И площадь > 0 (реальный треугольник). Складываем эти площади по ходу, сравниваем...
интересно, как именно дергать? по первым трем - еще понятно, а все возможные комбинации как же перебрать?
и еще непонятно, как сделать проверку, когда 3 точки не лежат на одной прямой в случае, если прямая под углом к какой нибудь оси.
Ответить с цитированием
  (#4 (permalink)) Старый
aag aag вне форума
ушёл... не вернётся)))
 
Сообщений: 3,400
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
По умолчанию 10.11.2011, 23:49

Ага... Давайте тогда по простому. Есть список точек. Из этого списка точек делаем список всех возможных треугольников. Уже с площадями...

треугольник(СписокТочек,Треугольник):- get3(3,СписокТочек, ТриТочки), D=ЯнеПомнюПлощадьПоТрёмТочкам(ТриТочки), D>0, Треугольник=[D|ТриТочки].

get3(0,_,[]):- !.
get3(A,[B|C],[B|D]):- E=A-1, get3(E,C,D).
get3(A,[_|B],C):- get3(A,B,C).

findAll(X,треугольник(СписокТочек,X),СписокТреугол ьников) накидает в СписокТреугольников все возможные треугольники с отличной от 0 площадью(это Ваше "не лежат на одной прямой", если лежат, то площадь = 0. Чему равно площадь по трём точкам - это Вы сами пошукайте)))).
А дальше продолжим: дёргать из СпискаТреугольников нужное количество НЕПЕРЕСЕКАЮЩИХСЯ треугольников, складывать площади и т.д.

Пролог то какой?!)))
Ответить с цитированием
  (#5 (permalink)) Старый
zener zener вне форума
Member
 
Сообщений: 56
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.10.2010
По умолчанию 11.11.2011, 00:12

Цитата:
Сообщение от aag Посмотреть сообщение
Пролог то какой?!)))
5.1
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
aag aag вне форума
ушёл... не вернётся)))
 
Сообщений: 3,400
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
По умолчанию 11.11.2011, 00:21

Да нормально, хоть я в эту штуку ни разу не заглядывал))) Собирайте в список все треугольники, а тама будет видно....
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Остроугольные треугольники Irinka2012 Prolog 1 11.01.2012 20:53
Wi-Fi 2 точки подключения DiKey Wi-Fi и сети 1 23.09.2011 20:32
зеленые точки!!! Zoxan Видеокарты 11 09.07.2011 16:33
Освещенность 1 точки cqwery Программирование графики 1 14.06.2011 08:50
Точки по всему экрану suris2009 Видеокарты 10 28.05.2011 00:21
Седловые точки Стася Pascal 5 09.05.2011 15:38
Точки восстановления. vales11 Любые вопросы от новичков 3 13.01.2011 15:00
Настройка точки доступа movsesiv Wi-Fi и сети 6 25.11.2010 16:10
срочно нужна помощь. задача про треугольники Syndrome Prolog 1 21.11.2010 20:38
Игра точки как написать массив который хранит точки wenom C++ Builder 6 07.03.2007 00:57
Как соединить точки дугой точки Denalko Delphi 6 16.09.2005 22:10
Как треугольники в d3d neib Программирование графики 9 28.04.2004 01:41



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов