Из заданного множества точек на плоскости выбрать три разные точки A, B и C так, чтобы внутри треугольника ABC содержалось максимальное количество точ

@qliqli · Регистрация: 16.11.2009

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

Из заданного множества точек на плоскости выбрать три разные точки A, B и C так, чтобы внутри треугольника ABC содержалось максимальное количество точек этого множества. Исходные данные задать в видде файла. Проиллюстрировать задачу. (MathCad)

@Галина Борисовн · 27.05.2010, 14:16

Уважаемый, qliqli, Ваша задача довольно интересная. Предлагаю Вам первую подсказку.
Для того, чтобы выяснить находится ли точка Р внутри или вне треугольника, рассматриваются лучи из точки Р в последовательные вершины треугольника. Суммируются полученные углы. Если сумма углов равна 360 градусов или -360 градусов (знак зависит от направления обхода), то точка Р находится внутри треугольника. Если сумма углов равна нулю, то точка Р вне треугольника. Для пояснения даю рисунок.

@qliqli · 27.05.2010, 22:28 **[ТС]**

Уважаемая Галина Борисовна, большое спасибо за совет. Теперь я понял из чего и как мне надо формировать программный модуль, но у меня с ним большие проблемы( в частном случае с отдельными циклами в нем и с различными другими формированиями условий и переменных) =(

@Галина Борисовн · 27.05.2010, 22:54

Уважаемый, qliqli, Ваши затруднения понятны. Задача непростая. Необходимо, прежде всего, составить схему алгоритма. Угол между двумя лучами удобно рассчитывать с помощью функции atan2(x,y).
Так как показано на рисунке. Функция atan2(x,y) возвращает угол в радианах. Дерзайте!

@qliqli · 28.05.2010, 14:57 **[ТС]**

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

@Галина Борисовн · 28.05.2010, 15:31

Уважаемый, qliqli, я думаю, что Вам нужно будет программно перебрать все возможные треугольники, а их количество равно числу сочетаний из n элементов по 3 = n!/(3!*(n-3)!), и для каждого треугольника посчитать количество точек, в него попавших).

19.05.2011, 18:34

Здравствуйте) помогите пожалуйста решить в MathCAD задачу) Даны два множества точек на плоскости. Из первого множества выбрать три различные точки так, чтобы треугольник с вершинами в этих точках содержал (строго внутри себя) равное количество точек первого и второго множеств.

@di3zel · 19.05.2011, 21:06

Можно ещё проверять по площадям.
Берем каждую из точек и каждый из треугольников, если точка лежит в треугольнике, то сумма площадей трех маленьких треуг(образованных соединением этой точки с вершинами) равна площади основного треугольника.
Есть у меня такая задача, но она нуждается в небольшой доработке.
Нужно Вам?

@Symon · 12.01.2013, 16:14

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

Можно ещё проверять по площадям.
Берем каждую из точек и каждый из треугольников, если точка лежит в треугольнике, то сумма площадей трех маленьких треуг(образованных соединением этой точки с вершинами) равна площади основного треугольника.
Есть у меня такая задача, но она нуждается в небольшой доработке.
Нужно Вам?

Можно с экономить на вычислениях. Нужны не площади 4-х треуг., достаточно определить знаки 3-х "площадей".
Нужно Вам?

Новые блоги и статьи
Книги и учебные ресурсы по C# InfoMaster 08.01.2025 Базовые учебники и руководства Одной из лучших книг для начинающих является "C# 10 и . NET 6 для начинающих" Эндрю Троелсена и Филиппа Джепикса . Книга последовательно раскрывает основные концепции. . .	Что такое NullReferenceException и как исправить? InfoMaster 08.01.2025 NullReferenceException - одно из самых распространенных исключений, с которым сталкиваются разработчики на C#. Это исключение возникает при попытке обратиться к членам объекта (методам, свойствам или. . .	Что такое Null Pointer Exception (NPE) и как это исправить? InfoMaster 08.01.2025 Null Pointer Exception (NPE) - это одно из самых распространенных исключений в Java, которое возникает при попытке использовать ссылку на объект, значение которой равно null. Это исключение относится. . .	Русский язык в консоли C++ InfoMaster 08.01.2025 При разработке программ на C++ одной из частых проблем, с которой сталкиваются русскоязычные программисты, является корректное отображение кириллицы в консольных приложениях. Эта проблема особенно. . .	Telegram бот на C# InfoMaster 08.01.2025 Разработка ботов для Telegram стала неотъемлемой частью современной экосистемы мессенджеров. C# предоставляет мощный и удобный инструментарий для создания разнообразных ботов, от простых. . .	Использование GraphQL в Go (Golang) InfoMaster 08.01.2025 Go (Golang) является одним из наиболее популярных языков программирования, используемых для создания высокопроизводительных серверных приложений. Его архитектурные особенности и встроенные. . .
Что лучше использовать при создании класса в Java: сеттеры или конструктор? Alexander-7 08.01.2025 Вопрос подробнее: На вопрос: «Когда одновременно создаются конструктор и сеттеры в классе – это нормально?» куратор уточнил: «Ваш класс может вообще не иметь сеттеров, а только конструктор и геттеры. . .	Как работать с GraphQL на TypeScript InfoMaster 08.01.2025 Введение в GraphQL и TypeScript В современной разработке веб-приложений GraphQL стал мощным инструментом для создания гибких и эффективных API. В сочетании с TypeScript, эта технология. . .	Счётчик на базе сумматоров + регистров и генератора сигналов согласования. Hrethgir 07.01.2025 Создан с целью проверки скорости асинхронной логики: ранее описанного сумматора и предополагаемых fast регистров. Регистры созданы на базе ранее описанного, предполагаемого fast триггера. То-есть. . .	Как перейти с Options API на Composition API в Vue.js BasicMan 06.01.2025 Почему переход на Composition API актуален В мире современной веб-разработки фреймворк Vue. js продолжает эволюционировать, предлагая разработчикам все более совершенные инструменты для создания. . .	Архитектура современных процессоров inter-admin 06.01.2025 Процессор (центральный процессор, ЦП) является основным вычислительным устройством компьютера, которое выполняет обработку данных и управляет работой всех остальных компонентов системы. Архитектура. . .	История создания реляционной модели баз данных, правила Кодда Programming 06.01.2025 Предпосылки создания реляционной модели В конце 1960-х годов компьютерная индустрия столкнулась с серьезными проблемами в области управления данными. Существовавшие на тот момент модели данных -. . .

@qliqli 0 / 0 / 1 Регистрация: 16.11.2009 Сообщений: 39
		1
	Из заданного множества точек на плоскости выбрать три разные точки A, B и C так, чтобы внутри треугольника ABC содержалось максимальное количество точ 26.05.2010, 22:15. Показов 3145. Ответов 8 Метки нет (Все метки) Из заданного множества точек на плоскости выбрать три разные точки A, B и C так, чтобы внутри треугольника ABC содержалось максимальное количество точек этого множества. Исходные данные задать в видде файла. Проиллюстрировать задачу. (MathCad) 0

@Галина Борисовн 2834 / 2131 / 86 Регистрация: 02.05.2010 Сообщений: 3,195
	27.05.2010, 14:16	2
	Уважаемый, qliqli, Ваша задача довольно интересная. Предлагаю Вам первую подсказку. Для того, чтобы выяснить находится ли точка Р внутри или вне треугольника, рассматриваются лучи из точки Р в последовательные вершины треугольника. Суммируются полученные углы. Если сумма углов равна 360 градусов или -360 градусов (знак зависит от направления обхода), то точка Р находится внутри треугольника. Если сумма углов равна нулю, то точка Р вне треугольника. Для пояснения даю рисунок. Миниатюры 0

@qliqli 0 / 0 / 1 Регистрация: 16.11.2009 Сообщений: 39
	27.05.2010, 22:28 [ТС]	3
	Уважаемая Галина Борисовна, большое спасибо за совет. Теперь я понял из чего и как мне надо формировать программный модуль, но у меня с ним большие проблемы( в частном случае с отдельными циклами в нем и с различными другими формированиями условий и переменных) =( 0

@Галина Борисовн 2834 / 2131 / 86 Регистрация: 02.05.2010 Сообщений: 3,195
	27.05.2010, 22:54	4
	Уважаемый, qliqli, Ваши затруднения понятны. Задача непростая. Необходимо, прежде всего, составить схему алгоритма. Угол между двумя лучами удобно рассчитывать с помощью функции atan2(x,y). Так как показано на рисунке. Функция atan2(x,y) возвращает угол в радианах. Дерзайте! Миниатюры 1

@qliqli 0 / 0 / 1 Регистрация: 16.11.2009 Сообщений: 39
	28.05.2010, 14:57 [ТС]	5
	А воообще мне точки для составления треугольника по условию самостоятельно выбирать или как? также в задаче этой надо подсчитать количество этих точек. 0

@Галина Борисовн 2834 / 2131 / 86 Регистрация: 02.05.2010 Сообщений: 3,195
	28.05.2010, 15:31	6
	Уважаемый, qliqli, я думаю, что Вам нужно будет программно перебрать все возможные треугольники, а их количество равно числу сочетаний из n элементов по 3 = n!/(3!*(n-3)!), и для каждого треугольника посчитать количество точек, в него попавших). 0

maratik_93
	19.05.2011, 18:34	7
	Здравствуйте) помогите пожалуйста решить в MathCAD задачу) Даны два множества точек на плоскости. Из первого множества выбрать три различные точки так, чтобы треугольник с вершинами в этих точках содержал (строго внутри себя) равное количество точек первого и второго множеств.

@di3zel 7 / 7 / 2 Регистрация: 24.05.2009 Сообщений: 51
	19.05.2011, 21:06	8
	Можно ещё проверять по площадям. Берем каждую из точек и каждый из треугольников, если точка лежит в треугольнике, то сумма площадей трех маленьких треуг(образованных соединением этой точки с вершинами) равна площади основного треугольника. Есть у меня такая задача, но она нуждается в небольшой доработке. Нужно Вам? 0

@Symon $Эксперт по математике/физике$ 2615 / 2229 / 684 Регистрация: 29.09.2012 Сообщений: 4,578 Записей в блоге: 13
	12.01.2013, 16:14	9
	Сообщение от di3zel Можно ещё проверять по площадям. Берем каждую из точек и каждый из треугольников, если точка лежит в треугольнике, то сумма площадей трех маленьких треуг(образованных соединением этой точки с вершинами) равна площади основного треугольника. Есть у меня такая задача, но она нуждается в небольшой доработке. Нужно Вам? Можно с экономить на вычислениях. Нужны не площади 4-х треуг., достаточно определить знаки 3-х "площадей". Нужно Вам? 0