Найти подмножество, содержащее ровно M точек, центр тяжести которого находится наиболее близко к началу координат

@pampam · Регистрация: 22.01.2014

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

Если честно я как то не могу полностью понять суть задачи, помогите желательно кодом мне срочно надо
Заранее спасибо)

На плоскости задано множество N (1<N≤20) материальных точек. Найти такое подмножество этого множества, содержащее ровно M (M<N) точек, центр тяжести которого находится наиболее близко к началу координат.
Формат входных данных
В первой строке – числа N и M. В последующих N строках точки, для которых заданы координаты и масса.
Формат выходных данных
Выдать номера точек в порядке следования, попавших в искомое множество.
Пример
input
4 3
5 3 5
3 1 1
3 3 3
1 2 2

output
2 3 4

Байт · 15.12.2014, 12:47

pampam, А в чем сложности? Генеришь все возможные сочетания из N по M (на форуме код такой генерации точно был) для каждого считаешь центр тяжести, выбираешь лучший...

@pampam · 18.12.2014, 04:01 **[ТС]**

а как вычислять центр тяжести? я вот чего понять не могу

@MDLee · 18.12.2014, 04:07

pampam
а как вычислять центр тяжести? я вот чего понять не могу - можешь просто считать эвклидовое растоние от точки до начала координат. в данном случае корень от сумм квадравтов координат

а где в вашей задаче условие на границу подмножества, из ходя из условия все точки находятся близко к началу координат

@_Ivana · 18.12.2014, 09:37

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

а как вычислять центр тяжести? я вот чего понять не могу

Как взвешенную сумму всех координат с равными весами - в народе среднее арифметическое.

Байт · 18.12.2014, 09:59

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

а как вычислять центр тяжести? я вот чего понять не могу

Просто, чтоб ясность внести. Пусть наши точки (x₁, y₁) ... (x_n,y_n)
x_c = (x₁ + ... x_n)/n
y_c = аналогично

@enuvin · 21.10.2017, 12:18

Здравствуйте, извините, что поднял эту древнюю тему, но я одно понять не могу. Вот например, первая точка х=5 у=3 и третья переменная(5) это ось z или масса точки?

@MansMI · 21.10.2017, 12:29

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

заданы координаты и масса.

...

@enuvin · 21.10.2017, 12:34

Тогда как связать координаты и среднеарифметическую массу?

Байт · 21.10.2017, 13:12

x_c = (x₁*m₁ + ... x_n*m_n)/n

@MansMI · 21.10.2017, 13:15

из школы:"а размерность ты проверил?"

Байт · 21.10.2017, 13:18

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

а размерность ты проверил?

Да, погорячился...

x_c = (x₁*m₁+ ... + x_n*m_n)/(m₁+...+m_n)

@enuvin · 21.10.2017, 14:40

Понял, спасибо

Новые блоги и статьи Все статьи Все блоги /
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек SDL3 и Box2D из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия SDL 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual. . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»

@pampam 0 / 0 / 0 Регистрация: 22.01.2014 Сообщений: 11

	Найти подмножество, содержащее ровно M точек, центр тяжести которого находится наиболее близко к началу координат 15.12.2014, 11:39. Показов 2014. Ответов 12 Метки нет (Все метки) Если честно я как то не могу полностью понять суть задачи, помогите желательно кодом мне срочно надо Заранее спасибо) На плоскости задано множество N (1<N≤20) материальных точек. Найти такое подмножество этого множества, содержащее ровно M (M<N) точек, центр тяжести которого находится наиболее близко к началу координат. Формат входных данных В первой строке – числа N и M. В последующих N строках точки, для которых заданы координаты и масса. Формат выходных данных Выдать номера точек в порядке следования, попавших в искомое множество. Пример input 4 3 5 3 5 3 1 1 3 3 3 1 2 2 output 2 3 4 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	15.12.2014, 12:47
	pampam, А в чем сложности? Генеришь все возможные сочетания из N по M (на форуме код такой генерации точно был) для каждого считаешь центр тяжести, выбираешь лучший... 0

@pampam 0 / 0 / 0 Регистрация: 22.01.2014 Сообщений: 11
	18.12.2014, 04:01 [ТС]
	а как вычислять центр тяжести? я вот чего понять не могу 0

@MDLee 15 / 5 / 1 Регистрация: 17.12.2014 Сообщений: 60
	18.12.2014, 04:07
	pampam а как вычислять центр тяжести? я вот чего понять не могу - можешь просто считать эвклидовое растоние от точки до начала координат. в данном случае корень от сумм квадравтов координат а где в вашей задаче условие на границу подмножества, из ходя из условия все точки находятся близко к началу координат 0

@enuvin 0 / 0 / 0 Регистрация: 30.03.2017 Сообщений: 18
	21.10.2017, 12:18
	Здравствуйте, извините, что поднял эту древнюю тему, но я одно понять не могу. Вот например, первая точка х=5 у=3 и третья переменная(5) это ось z или масса точки? 0

@enuvin 0 / 0 / 0 Регистрация: 30.03.2017 Сообщений: 18
	21.10.2017, 12:34
	Тогда как связать координаты и среднеарифметическую массу? 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	21.10.2017, 13:12
	x_c = (x₁m₁ + ... x_nm_n)/n 0

@MansMI 1617 / 1182 / 553 Регистрация: 08.01.2012 Сообщений: 4,561
	21.10.2017, 13:15
	из школы:"а размерность ты проверил?" 1

@enuvin 0 / 0 / 0 Регистрация: 30.03.2017 Сообщений: 18
	21.10.2017, 14:40
	Понял, спасибо 0