0 / 0 / 1
Регистрация: 16.11.2009
Сообщений: 39
|
|
Из заданного множества точек на плоскости выбрать три разные точки A, B и C так, чтобы внутри треугольника ABC содержалось максимальное количество точ26.05.2010, 22:15. Показов 3184. Ответов 8
Метки нет Все метки)
(
Из заданного множества точек на плоскости выбрать три разные точки A, B и C так, чтобы внутри треугольника ABC содержалось максимальное количество точек этого множества. Исходные данные задать в видде файла. Проиллюстрировать задачу. (MathCad)
0
|
26.05.2010, 22:15 | |
Ответы с готовыми решениями:
8
Из заданного множества точек на плоскости выбрать три разные точки А В С так, чтобы внутри треугольника АВС содержалось максимальное количество точек. Выбрать из множества три разные точки так, чтобы внутри треугольника содержалось максимальное количество точек Выбрать три разные точки А, В, С так, чтобы внутри треугольника АВС содержалось максимальное количество точек |
![]() 2835 / 2132 / 86
Регистрация: 02.05.2010
Сообщений: 3,195
|
|
27.05.2010, 14:16 | |
Уважаемый, qliqli, Ваша задача довольно интересная. Предлагаю Вам первую подсказку.
Для того, чтобы выяснить находится ли точка Р внутри или вне треугольника, рассматриваются лучи из точки Р в последовательные вершины треугольника. Суммируются полученные углы. Если сумма углов равна 360 градусов или -360 градусов (знак зависит от направления обхода), то точка Р находится внутри треугольника. Если сумма углов равна нулю, то точка Р вне треугольника. Для пояснения даю рисунок.
0
|
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
|
![]() 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 задачу) Даны два множества точек на плоскости. Из первого множества выбрать три различные точки так, чтобы треугольник с вершинами в этих точках содержал (строго внутри себя) равное количество точек первого и второго множеств.
|
7 / 7 / 2
Регистрация: 24.05.2009
Сообщений: 51
|
|
19.05.2011, 21:06 | |
Можно ещё проверять по площадям.
Берем каждую из точек и каждый из треугольников, если точка лежит в треугольнике, то сумма площадей трех маленьких треуг(образованных соединением этой точки с вершинами) равна площади основного треугольника. Есть у меня такая задача, но она нуждается в небольшой доработке. Нужно Вам?
0
|
![]() |
|
12.01.2013, 16:14 | |
Можно с экономить на вычислениях. Нужны не площади 4-х треуг., достаточно определить знаки 3-х "площадей".
Нужно Вам?
0
|
12.01.2013, 16:14 | ||||||
Помогаю со студенческими работами здесь
9
Выбрать три точки из множества точек на плоскости так, чтобы была минимальной разность между количествами точек внутри и вне треугольника Выбрать три различные точки из заданного множества точек на плоскости так, чтобы была минимальной разность между количествами точек, внутри и снаружи. Из заданного множества точек на плоскости выбрать три разные точки A, B, C Даны два множества точек на плоскости. Выбрать три точки так, чтобы треугольник с вершинами в этих точках содержал равное количество точек Искать еще темы с ответами Или воспользуйтесь поиском по форуму:
|
|
Новые блоги и статьи
![]() |
||||
Антипаттерны микросервисной архитектуры
ArchitectMsa 03.04.2025
Хорошо спроектированная микросервисная система может выдержать испытание временем, оставаясь гибкой, масштабируемой и устойчивой к большинству проблем. Такая архитектура обладает высоким уровнем. . .
|
std::mutex в C++: Советы и примеры использования
bytestream 03.04.2025
std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .
|
Не удержался от оценки концепции двигателя Стирлинга.
Hrethgir 03.04.2025
Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .
|
Метод с двумя буферами (или double buffering) или ping-pong buffering
Hrethgir 02.04.2025
Из ответов LM модели.
Метод, который предполагает использование двух массивов для хранения промежуточных результатов сложения векторов, обычно применяется в сценариях, где необходимо минимизировать. . .
|
На любовном киберфронте
Alexander-7 01.04.2025
Недавно на одном малоизвестном сайте знакомств мною заинтересовалась девушка:
«Текст немного странный. Но, судя по адресу почты, иностранка», – подумал я. Поколебавшись пару суток, я ответил ей:. . .
|
Как работает Node.js изнутри
run.dev 29.03.2025
Node. js изменил подход к разработке веб-приложений, позволив использовать JavaScript не только на стороне клиента, но и на сервере. Созданный в 2009 году Райаном Далем, этот открытый,. . .
|
Моки в Python: Mock Object Library
py-thonny 29.03.2025
Тестирование кода требует особого подхода, когда речь идёт о компонентах, взаимодействующих с внешним миром. Мы часто сталкиваемся с непредсказуемостью HTTP-запросов, чтением данных из базы или. . .
|
JavaScript: Управление памятью и улучшение производительности
run.dev 29.03.2025
В отличие от низкоуровневых языков программирования, JavaScript не требует ручного выделения и освобождения памяти. Здесь работает автоматический сборщик мусора, который определяет, какие объекты. . .
|
Мультитенантная архитектура со SpringBoot и PostgreSQL
ArchitectMsa 29.03.2025
SaaS-приложения редко обслуживают одного клиента и обычно они должны поддерживать множество организаций, каждая из которых работает в своём изолированном пространстве. Мультитенантная архитектура. . .
|
std::span в C++: Производительность и лучшие практики
NullReferenced 28.03.2025
std::span — одно из самых недооценённых нововведений стандарта C++20, которое радикально меняет подход к работе с непрерывными последовательностями данных. По сути, это невладеющее представление. . .
|