Выбрать такие три точки, что, будь они вершинами треугольника, выполнялось бы условие

@lovepanda · Регистрация: 21.05.2015

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

Среди заданных точек множини на плоскости выбрать 3 таких чтоб треугольник, вершины которого эти точки местил бы наибольшее количество точек. Помогите плс как математически решать, программу постараюсь сам сделать))

@tera94 · 21.05.2015, 18:52

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

@lovepanda · 21.05.2015, 18:59 **[ТС]**

да я думаю так и надо, просто не совсем понимаю как с математической точки зрения его решать, естественно и программу не напишу.

@tera94 · 21.05.2015, 19:02

Интересная задача, но понятно, что не факт, что такой треугольник единственный)

@lovepanda · 21.05.2015, 19:04 **[ТС]**

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

@tera94 · 21.05.2015, 19:08

не знаю как через окружность, но в голову приходит только тупой перебор всех треугольников

@lovepanda · 21.05.2015, 19:39 **[ТС]**

Лол плоскость ты задаешь сам, и она может быть любого размера, что ты собрался перебирать?

@tera94 · 21.05.2015, 19:56

треугольники вершины которых из заданного множества
при мощности множества = n количество комбинаций равно С из n по 3
вроде так

Добавлено через 11 минут
мой вариант решения таков: перебираем треугольники, по вершинам строим уравнения прямых, по уравнениям прямых исключаем из ненужных полуплоскостей точки множества, точки которые входят во все 3 нужные полуплоскости - это точки внутри треугольника. выбираем треугольник с наибольшим количеством точек. Уверен есть решения попроще.

@lovepanda 0 / 0 / 0 Регистрация: 21.05.2015 Сообщений: 18
		1
	Выбрать такие три точки, что, будь они вершинами треугольника, выполнялось бы условие 21.05.2015, 17:57. Показов 722. Ответов 7 Метки нет (Все метки) Среди заданных точек множини на плоскости выбрать 3 таких чтоб треугольник, вершины которого эти точки местил бы наибольшее количество точек. Помогите плс как математически решать, программу постараюсь сам сделать)) 0

@tera94 1 / 1 / 4 Регистрация: 28.11.2014 Сообщений: 36
	21.05.2015, 18:52	2
	не совсем понял, нужно выбрать вершины для такого треугольника, внутри которого оказалось бы больше всего точек из того же множества? 0

@lovepanda 0 / 0 / 0 Регистрация: 21.05.2015 Сообщений: 18
	21.05.2015, 18:59 [ТС]	3
	да я думаю так и надо, просто не совсем понимаю как с математической точки зрения его решать, естественно и программу не напишу. 0

@tera94 1 / 1 / 4 Регистрация: 28.11.2014 Сообщений: 36
	21.05.2015, 19:02	4
	Интересная задача, но понятно, что не факт, что такой треугольник единственный) 0

@lovepanda 0 / 0 / 0 Регистрация: 21.05.2015 Сообщений: 18
	21.05.2015, 19:04 [ТС]	5
	ну я думал чтоб сделать как-то через вписанный треугольник в окружность , но думаю мб ошибаюсь. 0

@tera94 1 / 1 / 4 Регистрация: 28.11.2014 Сообщений: 36
	21.05.2015, 19:08	6
	не знаю как через окружность, но в голову приходит только тупой перебор всех треугольников 0

@lovepanda 0 / 0 / 0 Регистрация: 21.05.2015 Сообщений: 18
	21.05.2015, 19:39 [ТС]	7
	Лол плоскость ты задаешь сам, и она может быть любого размера, что ты собрался перебирать? 0

@tera94 1 / 1 / 4 Регистрация: 28.11.2014 Сообщений: 36
	21.05.2015, 19:56	8
	треугольники вершины которых из заданного множества при мощности множества = n количество комбинаций равно С из n по 3 вроде так Добавлено через 11 минут мой вариант решения таков: перебираем треугольники, по вершинам строим уравнения прямых, по уравнениям прямых исключаем из ненужных полуплоскостей точки множества, точки которые входят во все 3 нужные полуплоскости - это точки внутри треугольника. выбираем треугольник с наибольшим количеством точек. Уверен есть решения попроще. 0