Задачка про треугольники и точки

@_nikita · Регистрация: 04.10.2013

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

Доброго времени суток. Необходимо написать программу, суть такова: дано N треугольников (1<=N<=100)на плоскости (заданы координатами вершин - 3 пары действительных чисел) - необходимо найти такую точку на плоскости, которую включало бы в себя максимальное количество треугольников.
Точка принадлежит треугольнику, если она принадлежит области внутри треугольника или одной из его сторон.
Треугольник может быть вырожден в отрезок или точку.

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

Заранее благодарю за помощь.

@Qwertiy · 04.10.2013, 23:02

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

перебирать все точки плоскости (разумеется, с каким-то шагом) и для них просчитывать

Почти. Перебирать все концы отрезков и точки их пересечения.

@Igor3D · 05.10.2013, 10:29

Не совсем "оно", но близко, стоит глянуть
http://e-maxx.ru/algo/triangles_union

@_nikita · 06.10.2013, 11:56 **[ТС]**

спасибо за советы, буду разбираться.

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@_nikita 0 / 0 / 0 Регистрация: 04.10.2013 Сообщений: 2

	Задачка про треугольники и точки 04.10.2013, 21:25. Показов 832. Ответов 3 Метки нет (Все метки) Доброго времени суток. Необходимо написать программу, суть такова: дано N треугольников (1<=N<=100)на плоскости (заданы координатами вершин - 3 пары действительных чисел) - необходимо найти такую точку на плоскости, которую включало бы в себя максимальное количество треугольников. Точка принадлежит треугольнику, если она принадлежит области внутри треугольника или одной из его сторон. Треугольник может быть вырожден в отрезок или точку. Не могу понять, как подступиться к решению? Единственное, что пришло в голову - перебирать все точки плоскости (разумеется, с каким-то шагом) и для них просчитывать, в скольких треугольниках они лежат. Но объем вычислений получиться до безобразия большим. Наверняка же есть какой-то более простой способ, алгоритм, теория, которые помогли бы в решении данной задачи? Заранее благодарю за помощь. 0

@Igor3D 1964 / 820 / 114 Регистрация: 01.10.2012 Сообщений: 4,782 Записей в блоге: 2
	05.10.2013, 10:29
	Не совсем "оно", но близко, стоит глянуть http://e-maxx.ru/algo/triangles_union 1

@_nikita 0 / 0 / 0 Регистрация: 04.10.2013 Сообщений: 2
	06.10.2013, 11:56 [ТС]
	спасибо за советы, буду разбираться. 0