Треугольники и перебор точек

@SDmaN · Регистрация: 22.07.2011

Студворк — интернет-сервис помощи студентам

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

Допустим, что точки даны в виде массива типа Point.
Интересует только перебор точек. Я так понимаю, что если из всех точек выбирать по 9 для образования треугольников, то получаются размещения из N по 9, где N - размер массива. Чтобы было где искать, нужно минимум 9 точек. Число размещений из 9 по 9 равно 362880. Вообще прав ли я? И если нет, то направьте меня на верный путь. Буду не против кода на C++.

Байт · 03.02.2015, 10:34

Сообщение от _Ivana

условия лежания точек по одну сторону конечно неизвестно

При подстановке координат точек в уравнение прямой получается одинаковый знак.

@kravam · 03.02.2015, 23:17

Кто-нибудь написал код? Я написал, хочу проверить. Под спойлером простыня вида:

0 0 0 1 1 1 2 2 2
0 0 0 1 1 2 1 2 2
0 0 0 1 1 2 2 1 2
... и т. д.

Суть: имеем точки с номерами от 0 до 8. Если взглянуть на отрывок из простыни (выше), то увидим треугольники, состоящие из точек с номерами (в первых скобках номера нолей, во вторых номера единиц, в третьих номера двоек):

(0,1,2), (3,4,5), (6,7,8)- один треугольник
(0,1,2), (3,4,6), (5,7,8)- второй треугольник
(0,1,2), (3,4,7), (5,6,8)- третий треугольник

и так далее. Всего 215 вариантов. Прав ли я? Если мой код корректен, то он работает с любым количеством n-угольников, но прежде хочу проверить. Опровергать собственной простынёй или указанием отсутствующих треугольников;

вывод

0 0 0 1 1 1 2 2 2
0 0 0 1 1 2 1 2 2
0 0 0 1 1 2 2 1 2
0 0 0 1 1 2 2 2 1
0 0 0 1 2 1 1 2 2
0 0 0 1 2 1 2 1 2
0 0 0 1 2 1 2 2 1
0 0 0 1 2 2 1 1 2
0 0 0 1 2 2 1 2 1
0 0 0 1 2 2 2 1 1
0 0 1 0 1 1 2 2 2
0 0 1 0 1 2 1 2 2
0 0 1 0 1 2 2 1 2
0 0 1 0 1 2 2 2 1
0 0 1 0 2 1 1 2 2
0 0 1 0 2 1 2 1 2
0 0 1 0 2 1 2 2 1
0 0 1 0 2 2 1 1 2
0 0 1 0 2 2 1 2 1
0 0 1 0 2 2 2 1 1
0 0 1 1 0 1 2 2 2
0 0 1 1 0 2 1 2 2
0 0 1 1 0 2 2 1 2
0 0 1 1 0 2 2 2 1
0 0 1 1 1 0 2 2 2
0 0 1 1 2 0 1 2 2
0 0 1 1 2 0 2 1 2
0 0 1 1 2 0 2 2 1
0 0 1 1 2 1 0 2 2
0 0 1 1 2 2 0 1 2
0 0 1 1 2 2 0 2 1
0 0 1 1 2 2 1 0 2
0 0 1 1 2 2 2 0 1
0 0 1 1 2 2 2 1 0
0 0 1 2 0 1 1 2 2
0 0 1 2 0 1 2 1 2
0 0 1 2 0 1 2 2 1
0 0 1 2 0 2 1 1 2
0 0 1 2 0 2 1 2 1
0 0 1 2 0 2 2 1 1
0 0 1 2 1 0 1 2 2
0 0 1 2 1 0 2 1 2
0 0 1 2 1 0 2 2 1
0 0 1 2 1 1 0 2 2
0 0 1 2 1 2 0 1 2
0 0 1 2 1 2 0 2 1
0 0 1 2 1 2 1 0 2
0 0 1 2 1 2 2 0 1
0 0 1 2 1 2 2 1 0
0 0 1 2 2 0 1 1 2
0 0 1 2 2 0 1 2 1
0 0 1 2 2 0 2 1 1
0 0 1 2 2 1 0 1 2
0 0 1 2 2 1 0 2 1
0 0 1 2 2 1 1 0 2
0 0 1 2 2 1 2 0 1
0 0 1 2 2 1 2 1 0
0 0 1 2 2 2 0 1 1
0 0 1 2 2 2 1 0 1
0 0 1 2 2 2 1 1 0
0 1 0 0 1 1 2 2 2
0 1 0 0 1 2 1 2 2
0 1 0 0 1 2 2 1 2
0 1 0 0 1 2 2 2 1
0 1 0 0 2 1 1 2 2
0 1 0 0 2 1 2 1 2
0 1 0 0 2 1 2 2 1
0 1 0 0 2 2 1 1 2
0 1 0 0 2 2 1 2 1
0 1 0 0 2 2 2 1 1
0 1 0 1 0 1 2 2 2
0 1 0 1 0 2 1 2 2
0 1 0 1 0 2 2 1 2
0 1 0 1 0 2 2 2 1
0 1 0 1 1 0 2 2 2
0 1 0 1 2 0 1 2 2
0 1 0 1 2 0 2 1 2
0 1 0 1 2 0 2 2 1
0 1 0 1 2 1 0 2 2
0 1 0 1 2 2 0 1 2
0 1 0 1 2 2 0 2 1
0 1 0 1 2 2 1 0 2
0 1 0 1 2 2 2 0 1
0 1 0 1 2 2 2 1 0
0 1 0 2 0 1 1 2 2
0 1 0 2 0 1 2 1 2
0 1 0 2 0 1 2 2 1
0 1 0 2 0 2 1 1 2
0 1 0 2 0 2 1 2 1
0 1 0 2 0 2 2 1 1
0 1 0 2 1 0 1 2 2
0 1 0 2 1 0 2 1 2
0 1 0 2 1 0 2 2 1
0 1 0 2 1 1 0 2 2
0 1 0 2 1 2 0 1 2
0 1 0 2 1 2 0 2 1
0 1 0 2 1 2 1 0 2
0 1 0 2 1 2 2 0 1
0 1 0 2 1 2 2 1 0
0 1 0 2 2 0 1 1 2
0 1 0 2 2 0 1 2 1
0 1 0 2 2 0 2 1 1
0 1 0 2 2 1 0 1 2
0 1 0 2 2 1 0 2 1
0 1 0 2 2 1 1 0 2
0 1 0 2 2 1 2 0 1
0 1 0 2 2 1 2 1 0
0 1 0 2 2 2 0 1 1
0 1 0 2 2 2 1 0 1
0 1 0 2 2 2 1 1 0
0 1 1 0 0 1 2 2 2
0 1 1 0 0 2 1 2 2
0 1 1 0 0 2 2 1 2
0 1 1 0 0 2 2 2 1
0 1 1 0 1 0 2 2 2
0 1 1 0 2 0 1 2 2
0 1 1 0 2 0 2 1 2
0 1 1 0 2 0 2 2 1
0 1 1 0 2 1 0 2 2
0 1 1 0 2 2 0 1 2
0 1 1 0 2 2 0 2 1
0 1 1 0 2 2 1 0 2
0 1 1 0 2 2 2 0 1
0 1 1 0 2 2 2 1 0
0 1 1 1 0 0 2 2 2
0 1 1 2 0 0 1 2 2
0 1 1 2 0 0 2 1 2
0 1 1 2 0 0 2 2 1
0 1 1 2 0 1 0 2 2
0 1 1 2 0 2 0 1 2
0 1 1 2 0 2 0 2 1
0 1 1 2 0 2 1 0 2
0 1 1 2 0 2 2 0 1
0 1 1 2 0 2 2 1 0
0 1 1 2 1 0 0 2 2
0 1 1 2 2 0 0 1 2
0 1 1 2 2 0 0 2 1
0 1 1 2 2 0 1 0 2
0 1 1 2 2 0 2 0 1
0 1 1 2 2 0 2 1 0
0 1 1 2 2 1 0 0 2
0 1 1 2 2 2 0 0 1
0 1 1 2 2 2 0 1 0
0 1 1 2 2 2 1 0 0
0 1 2 0 0 1 1 2 2
0 1 2 0 0 1 2 1 2
0 1 2 0 0 1 2 2 1
0 1 2 0 0 2 1 1 2
0 1 2 0 0 2 1 2 1
0 1 2 0 0 2 2 1 1
0 1 2 0 1 0 1 2 2
0 1 2 0 1 0 2 1 2
0 1 2 0 1 0 2 2 1
0 1 2 0 1 1 0 2 2
0 1 2 0 1 2 0 1 2
0 1 2 0 1 2 0 2 1
0 1 2 0 1 2 1 0 2
0 1 2 0 1 2 2 0 1
0 1 2 0 1 2 2 1 0
0 1 2 0 2 0 1 1 2
0 1 2 0 2 0 1 2 1
0 1 2 0 2 0 2 1 1
0 1 2 0 2 1 0 1 2
0 1 2 0 2 1 0 2 1
0 1 2 0 2 1 1 0 2
0 1 2 0 2 1 2 0 1
0 1 2 0 2 1 2 1 0
0 1 2 0 2 2 0 1 1
0 1 2 0 2 2 1 0 1
0 1 2 0 2 2 1 1 0
0 1 2 1 0 0 1 2 2
0 1 2 1 0 0 2 1 2
0 1 2 1 0 0 2 2 1
0 1 2 1 0 1 0 2 2
0 1 2 1 0 2 0 1 2
0 1 2 1 0 2 0 2 1
0 1 2 1 0 2 1 0 2
0 1 2 1 0 2 2 0 1
0 1 2 1 0 2 2 1 0
0 1 2 1 1 0 0 2 2
0 1 2 1 2 0 0 1 2
0 1 2 1 2 0 0 2 1
0 1 2 1 2 0 1 0 2
0 1 2 1 2 0 2 0 1
0 1 2 1 2 0 2 1 0
0 1 2 1 2 1 0 0 2
0 1 2 1 2 2 0 0 1
0 1 2 1 2 2 0 1 0
0 1 2 1 2 2 1 0 0
0 1 2 2 0 0 1 1 2
0 1 2 2 0 0 1 2 1
0 1 2 2 0 0 2 1 1
0 1 2 2 0 1 0 1 2
0 1 2 2 0 1 0 2 1
0 1 2 2 0 1 1 0 2
0 1 2 2 0 1 2 0 1
0 1 2 2 0 1 2 1 0
0 1 2 2 0 2 0 1 1
0 1 2 2 0 2 1 0 1
0 1 2 2 0 2 1 1 0
0 1 2 2 1 0 0 1 2
0 1 2 2 1 0 0 2 1
0 1 2 2 1 0 1 0 2
0 1 2 2 1 0 2 0 1
0 1 2 2 1 0 2 1 0
0 1 2 2 1 1 0 0 2
0 1 2 2 1 2 0 0 1
0 1 2 2 1 2 0 1 0
0 1 2 2 1 2 1 0 0
0 1 2 2 2 0 0 1 1
0 1 2 2 2 0 1 0 1
0 1 2 2 2 0 1 1 0
0 1 2 2 2 1 0 0 1
0 1 2 2 2 1 0 1 0
0 1 2 2 2 1 1 0 0

@kravam · 19.02.2015, 22:36

Работает с любым количеством n-угольников, перебор 3 треугольников даёт 280 вариантов. Кто может сделать лучше, пусть сделает лучше.

Новые блоги и статьи Все статьи Все блоги /
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .

@SDmaN 60 / 57 / 8 Регистрация: 22.07.2011 Сообщений: 436

	Треугольники и перебор точек 01.02.2015, 23:52. Показов 9673. Ответов 22 Метки нет (Все метки) Найти три треугольника с вершинами в заданном множестве точек на плоскости так, чтобы второй треугольник лежал строго внутри первого, а третий внутри второго. Допустим, что точки даны в виде массива типа Point. Интересует только перебор точек. Я так понимаю, что если из всех точек выбирать по 9 для образования треугольников, то получаются размещения из N по 9, где N - размер массива. Чтобы было где искать, нужно минимум 9 точек. Число размещений из 9 по 9 равно 362880. Вообще прав ли я? И если нет, то направьте меня на верный путь. Буду не против кода на C++. 0