Из заданного множества точек на плоскости выбрать три разные точки 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-х "площадей".
Нужно Вам?

Новые блоги и статьи Все статьи Все блоги /
Паттерны распределённых транзакций в Event-Driven микросервисах ArchitectMsa 05.04.2025 Современные программные системы всё чаще проектируются как совокупность взаимодействующих микросервисов. И хотя такой подход даёт множество преимуществ — масштабируемость, гибкость, устойчивость к. . .	Работа с объемным DOM в javascript Htext 04.04.2025 Сегодня прочитал статью тут о расходах памяти в JS, ее утечках и т. п. И вот что вспомнил из своей недавней практики. Может, кому пригодится. Хотя, в той статье об этом тоже есть. Дело в том, что я. . .	Оптимизация производительности Node.js с помощью кластеризации run.dev 04.04.2025 Масштабирование приложений для обработки тысяч и миллионов запросов — обыденная задача для многих команд. Node. js, благодаря своей асинхронной событийно-ориентированной архитектуре, стал популярной. . .	Управление зависимостями в Python с Poetry py-thonny 04.04.2025 Стандартный инструмент для установки пакетов в Python - pip - прекрасно справляется с базовыми сценариями: установил пакет командой pip install и используешь его. Но что произойдёт, когда разные. . .	Мониторинг с Prometheus в PHP Jason-Webb 04.04.2025 Prometheus выделяется среди других систем мониторинга своим подходом к сбору и хранению метрик. В отличие от New Relic, который использует агентный подход и отправляет данные во внешнее хранилище,. . .
Пакет Context в Golang: Управление потоками и ресурсами golander 04.04.2025 Работа с горутинами в Go часто напоминает управление непослушными детьми - они разбегаются кто куда, делают что хотят и не всегда завершаются вовремя. К счастью, в Go 1. 7 появился пакет context,. . .	Контейнеризация React приложений с Docker Reangularity 03.04.2025 Контейнеризация позволяет упаковать приложение со всеми его зависимостями в автономный контейнер, который можно запустить на любой платформе с установленным Docker. Это существенно упрощает процессы. . .	Свой попап в SwiftUI mobDevWorks 03.04.2025 SwiftUI, как декларативный фреймворк от Apple, предоставляет множество инструментов для создания пользовательских интерфейсов. В нашем распоряжении есть такие API как alerts, popovers, action sheets. . .	Антипаттерны микросервисной архитектуры ArchitectMsa 03.04.2025 Хорошо спроектированная микросервисная система может выдержать испытание временем, оставаясь гибкой, масштабируемой и устойчивой к большинству проблем. Такая архитектура обладает высоким уровнем. . .	std::mutex в C++: Советы и примеры использования bytestream 03.04.2025 std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .

@qliqli 0 / 0 / 1 Регистрация: 16.11.2009 Сообщений: 39

	Из заданного множества точек на плоскости выбрать три разные точки A, B и C так, чтобы внутри треугольника ABC содержалось максимальное количество точ 26.05.2010, 22:15. Показов 3186. Ответов 8 Метки нет (Все метки) Из заданного множества точек на плоскости выбрать три разные точки A, B и C так, чтобы внутри треугольника ABC содержалось максимальное количество точек этого множества. Исходные данные задать в видде файла. Проиллюстрировать задачу. (MathCad) 0

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

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

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

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

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

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

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

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