 |
|
|
 
|
|
Медианы 
| DmitryG. |
|
|||
|
Unregistered |
Пожалуйста, подскажите алгоритм решения задачи:
Дано четное число точек на плоскости, причем никакие три из них не лежат на одной прямой. Медианой этого множества точек называется прямая, соединяющая две точки множества и такая, что с обеих сторон от нее расположено равное число точек. Подсчитать количество медиан. Заранее спасибо! |
|||
|
||||
Загрузка ...
| Akina |
|
|||
|
Советчик  Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
Если N - количество точек, то количество медиан = N/2.
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| Fearless |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 264 Регистрация: 2.9.2004 Где: Питер Репутация: нет Всего: 4 |
полностью согласен c Akina
|
|||
|
||||
| 3,14 |
|
|||
 Эксперт Профиль Группа: Участник Клуба Сообщений: 1614 Регистрация: 18.6.2004 Где: Н. Новгород Репутация: нет Всего: 24 |
Точно не верно, вот контрпример, возьмём 4 точки С коор-ми: (0;0), (3;0), (0;3), (1,1) - там 3 медианы  -------------------- Может быть, это только мой бред, Может быть, жизнь не так хороша, Может быть, я не выйду на свет, Но я летал, когда пела душа... |
|||
|
||||
| val |
|
|||
 Program developer Профиль Группа: Участник Клуба Сообщений: 992 Регистрация: 14.1.2003 Где: г. Киев Репутация: 1 Всего: 7 |
3,14 прав... Надо еще подумать...
-------------------- Терпимость - величайшее благо человечества... Ярчайший признак интеллекта – постоянно хорошее настроение… |
|||
|
||||
| Dmitry G. |
|
|||
|
Unregistered |
А если бы точек было нечетное количество...?
Какого ваше мнение насчет задачи: решаема, нерешаема? |
|||
|
||||
| 3,14 |
|
|||
|
Эксперт Профиль Группа: Участник Клуба Сообщений: 1614 Регистрация: 18.6.2004 Где: Н. Новгород Репутация: нет Всего: 24 |
По любому задача решается полным перебором, вычислительная сложность алгоритма - вот в чём вопрос. Это сообщение отредактировал(а) 3,14 - 14.9.2004, 09:48 -------------------- Может быть, это только мой бред, Может быть, жизнь не так хороша, Может быть, я не выйду на свет, Но я летал, когда пела душа... |
|||
|
||||
| dargaard |
|
|||
 Опытный Профиль Группа: Экс. модератор Сообщений: 450 Регистрация: 7.5.2004 Репутация: нет Всего: 25 |
тогда будет 0 медиан - всегда с однои стороны будет четное кол-во точек а с другои нечетное (так как по условию три точки не могут быть на однои прямои) -------------------- Ты должна сделать добро из зла потому что его больше не из чего сделать. Р.П.Уоррен |
|||
|
||||
| dargaard |
|
|||
|
Опытный Профиль Группа: Экс. модератор Сообщений: 450 Регистрация: 7.5.2004 Репутация: нет Всего: 25 |
просто идея
сортируем точки (от меншего х-а к болшемы и от меншего y к болшему. например вышли у нас точки A,B,C,D) далше соединяем A-B-C-D-A если вышел выпуклыи многоугольник - то медиан будет N/2. а вот если он вогнутыи то не знаю , есть тока смутные предположения - по моему выидет что то типа N/2 + 1*V где V количество вогнутостеи. (предположение нет времени пока проверить) -------------------- Ты должна сделать добро из зла потому что его больше не из чего сделать. Р.П.Уоррен |
|||
|
||||
| 3,14 |
|
|||
|
Эксперт Профиль Группа: Участник Клуба Сообщений: 1614 Регистрация: 18.6.2004 Где: Н. Новгород Репутация: нет Всего: 24 |
извиняюсь если не правильно понял, вот результат такой сортировки : 1 - (0;0) 2 - (0;3) 3 - (1;1) 4 - (3;1) 5 - (3;3) 6 - (4;2) Соединяем : 1->2->3->4->5->6->1 - многоугольника не выходит, получаем пересечение -------------------- Может быть, это только мой бред, Может быть, жизнь не так хороша, Может быть, я не выйду на свет, Но я летал, когда пела душа... |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
Да, погорячился... количество медиан гарантированно
N/2 <= M <= N-1 Это можно доказать... а вот ПОДСЧИТАТЬ - это фактически НАЙТИ их все... тут кроме перебора вряд ли что придумаешь - вернее придумать можно, но вряд ли вычислительно это будет лучше прямого перебора... -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| dargaard |
|
|||
|
Опытный Профиль Группа: Экс. модератор Сообщений: 450 Регистрация: 7.5.2004 Репутация: нет Всего: 25 |
3,14
прогнал я немного - с чегота взял что так всегда получится многоугольник  бум думать дальше -------------------- Ты должна сделать добро из зла потому что его больше не из чего сделать. Р.П.Уоррен |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
1) Если все точки являются вершинами выпуклого многоугольника, тогда M = N/2
2) (пока только неоконченная мысль...) Из любого количества точек можно выбрать часть из них так, что они являются вершинами выпуклого многоугольника, описанного вокруг всех остальных точек. Правда как это прикрутить к РЕШЕНИЮ задачи - пока не знаю... -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| redrick |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 547 Регистрация: 7.1.2004 Где: Москва Репутация: нет Всего: 5 |
ребят, а откуда уверенность существования алгоритма лучше перебора ?
я вот в серьёз задумался над доказательством его отсутствия -------------------- Имею Мнение Хрен Оспоришь |
|||
|
||||
| dargaard |
|
|||
|
Опытный Профиль Группа: Экс. модератор Сообщений: 450 Регистрация: 7.5.2004 Репутация: нет Всего: 25 |
нет уверенности - просто полным перебором как то неинтересно, да и хочется верить что можно решить задачу не за N! переборов
-------------------- Ты должна сделать добро из зла потому что его больше не из чего сделать. Р.П.Уоррен |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0562 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |