Найти точку в к-мерном пространстве

@DarthLenin · Регистрация: 22.09.2013

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

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

@dikanev · 22.09.2013, 23:03

Пусть точек $https://www.cyberforum.ru/cgi-bin/latex.cgi?N$ . Решение в лоб (перебираем все пары точек, увеличиваем счетчик, если ровно одна из координат совпадает, в конце берем точки с максимальным значением счетчика) требует $https://www.cyberforum.ru/cgi-bin/latex.cgi?N^2\cdot k$ сравнений. Чтобы его сократить:

1. Сортируем точки по каждой из координат. Теперь точки у которых совпадает одна из координат лежат рядом в соответствующем массиве.

2. Перебираем точки
2.1. Каждую ищем в отсортированных массивах.

2.2. Составляем список точек, совпадающих по координате с данной.

2.3. Считаем точки, встречающиеся в этом списке ровно один раз. Увеличиваем на эту величину счетчик для текущей точки и на 1 для всех встречающихся один раз точек.

2.4. Удаляем текущую точку из отсортированных массивов.

3. Берем точки с максимальным значением счетчика.

Получаем сложность порядка $https://www.cyberforum.ru/cgi-bin/latex.cgi?N\log_{2}N\cdot k$ .

@DarthLenin · 23.09.2013, 00:37 **[ТС]**

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

Пусть точек $https://www.cyberforum.ru/cgi-bin/latex.cgi?N$ . Решение в лоб (перебираем все пары точек, увеличиваем счетчик, если ровно одна из координат совпадает, в конце берем точки с максимальным значением счетчика)

Может получиться так, что нужной точки нет в исходном массиве. Пример датасета для 2-мерного пространства:
3,3 1,3 3,3 0,2 2,2 1,3
Ответом здесь будут точки 0,3 и 2,3

Добавлено через 8 минут
Замечу, что для 2мерного случая решение несложное, но с обощением на к-мерность возникают проблемы. Например, для 3мерного случая нам придется рассматривать каждую плоскость соответствующую 3ей координате. Собственно вопрос в том, как избежать такого перебора.
Кроме того, если ровно одна координата совпадает, то через такие точки нельзя провести прямую параллельную базису. Если ровно одна координата различается, тогда можно.

@dikanev · 23.09.2013, 01:15

Вижу, что я неправильно понял условие задачи и предложил алгоритм для поиска наилучшей точки из отмеченных. Надо еще подумать, но уже поздно. Завтра подумаю.

@Qwertiy · 23.09.2013, 11:41

Имея set <все_точки>, для каждой размерности сохранить map <координата, количество>. Последовательно для каждой пары осей перебираем точку из их map'ов. Полученная точка однозначно оределяет все вектора - считаем для них число точек, проверив дополнительно существует ли точка, которая является пересечением осей. Ассимптотика O(n^4).

@Igor3D · 23.09.2013, 12:17

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

Имея set <все_точки>, для каждой размерности сохранить map <координата, количество>. Последовательно для каждой пары осей перебираем точку из их map'ов. Полученная точка однозначно оределяет все вектора - считаем для них число точек, проверив дополнительно существует ли точка, которая является пересечением осей. Ассимптотика O(n^4).

Как-то жирно, ресурсозатратно (в духе высокоуровневых языков). Я бы сортировал указатели на точки по x, y, z. Тогда образуется такая структурка

C++    
        
    Скопировано
1
2
3
struct CLine {
 int mBeg, mEnd;   // индекс в сортированном массиве, все точки от mBeg до mEnd имеют одинаковые x и y, разный z
};

Сделал так же для всех комбинаций осей (y, z, x)(z, x, y) - имею 3 контейнера CLine. Отсортировал 2 последних по X. Иду по первому, двоичным поиском ищу в 2 последних. Повторяю эту процедуру число осей - 1 раз

@Qwertiy · 23.09.2013, 12:25

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

Я бы сортировал указатели на точки по x, y, z.

А ничего что пространство k-мерное, а не 3-мерное?

Добавлено через 3 минуты

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

Ассимптотика O(n^4).

Наврал.

Добавлено через 3 минуты
Ассимптотика O(k^3*n^2):
k^2 - перебор двух осей
n^2 - перебор точек на осях
k - подсчёт по оставшимся k-2 осям

@DarthLenin · 23.09.2013, 14:19 **[ТС]**

Имея set <все_точки>

Извиняюсь, я забыл упомянуть, что у нас может быть "несколько точек в одной точке". Так что на входе у нас multiset.

И я не слишком понял идею алгоритма. Не могли бы вы поподробнее описать что мы делаем на примере такого датасета:
1,3,3 2,1,3 3,3,3 1,0,2 1,2,2 0,1,3

Добавлено через 24 минуты
По сути задачу можно сформулировать так: найти такую точку, чтобы как можно большее число точек, подающихся на вход, отличалось от нее не более чем в 1 координате (на самом деле не более чем в d, но мне хотя бы при d=1 разобраться)

@Qwertiy · 23.09.2013, 16:14

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

Не могли бы вы поподробнее описать что мы делаем

Хм.. Кажется, я бред написал...
Думал, что так получится, но тут что-то не то

@Igor3D · 23.09.2013, 17:17

Давайте закончим с "первоначальной" постановкой задачи

Здесь все ясно: для каждой точки заводим k счетчиков (к - число осей). Сортируя точки k раз заполняем счетчики используя интервал точек сортированного массива отличающихся лишь по одной оси (последний ключ сортировки)

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

По сути задачу можно сформулировать так: найти такую точку, чтобы как можно большее число точек, подающихся на вход, отличалось от нее не более чем в 1 координате (на самом деле не более чем в d, но мне хотя бы при d=1 разобраться)

Не слабо...

Др словами - "найти точку с максимальной плотностью (d)"?

Добавлено через 3 минуты
Неясно что имеется ввиду. Напр 2 точки, расстояние между ними по x < 1. но по др оси напр 1000. Такие точки считаются или как?

@DarthLenin · 23.09.2013, 17:26 **[ТС]**

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

Не слабо...

Др словами - "найти точку с максимальной плотностью (d)"?

Ну...Не вполне уверен, что я правильно понимаю что такое плотность(d). Точки могут не быть сосредоточены геометрически близко. Но для 3мерного пространства это будет означать при d=1 что мы проводим через точку прямые, при d=2 - плоскости, при d=3 - куб (ну тут уже, очевидно, подойдет любая точка пространства). В общем, по-моему переформулировка получилась более понятной, т.к. она избавляет от геометрического смысла.

Добавлено через 4 минуты

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

Неясно что имеется ввиду. Напр 2 точки, расстояние между ними по x < 1. но по др оси напр 1000. Такие точки считаются или как?

Пространство, как я писал, дискретное. Допускаются только целые координаты. Если точки отличаются только по одной координате, неважно на сколько, то они лежат на одной прямой (параллельной какому-то базисному вектору) и следовательно считаются. Еще раз сформулирую: нужно найти такую точку, чтобы изменением ровно d координат (раз уж упомянул, будем говорить более обощенно, чтобы не путаться), можно было получить как можно больше точек из входного набора

@Igor3D · 23.09.2013, 17:54

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

Еще раз сформулирую: нужно найти такую точку, чтобы изменением ровно d координат (раз уж упомянул, будем говорить более обощенно, чтобы не путаться), можно было получить как можно больше точек из входного набора

А что есть "изменение ровно d координат"? Это шаг величиной d по одной из осей? Напр d = 1, точки (5, 5, 1)(5, 5, 2)(5, 5, 3) считаются, каждая точка имеет минимум 2 годных соседей. Тогда кстраивает предыдущее решение. Все это мне напоминпет воксели

@DarthLenin · 23.09.2013, 18:02 **[ТС]**

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

А что есть "изменение ровно d координат"? Это шаг величиной d по одной из осей?

Нет, это шаг произвольной длины по d осям
Например, из (5, 5, 1) можно получить (5, 5, 3) изменив одну координату (третью). Тут d=1. Например, между (5,5,1) и (5,3,2) d=2

@Igor3D · 23.09.2013, 18:14

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

Нет, это шаг произвольной длины по d осям
Например, из (5, 5, 1) можно получить (5, 5, 3) изменив одну координату (третью). Тут d=1. Например, между (5,5,1) и (5,3,2) d=2

То есть средняя точка имеет минимум 2 соседей, крайние - минимум 1. Все равно устраивает предыдущее решение

@DarthLenin · 23.09.2013, 18:22 **[ТС]**

Она может иметь больше 2 соседей, может вообще не иметь соседей, главное, чтобы все точки различались ровно в одних и тех же координатах.
Например, точки 0,0,1 0,0,2 0,0,3 0,0,4 все являются соседними друг другу т.к. любую из них можно получить изменением 1 координаты в любой другой. Возможно я просто не понимаю то, что вы хотите сказать. Если вы считаете, что ваш алгоритм работает, то не могли бы вы показать конкретные шаги на датасете который я писал выше. Напишу еще раз - 1,3,3 2,1,3 3,3,3 1,0,2 1,2,2 0,1,3.

@Igor3D · 23.09.2013, 19:46

(1,3,3) (2,1,3) (3,3,3) (1,0,2) (1,2,2) (0,1,3)

Сортируем по x, y, z
(0,1,3) (1,0,2) (1,2,2) (1,3,3) (2,1,3) (3,3,3) - никакие 2 точки не лежат на оси Z

Сортируем по y, z, x
(1,0,2) (0,1,3) (2,1,3) (1,2,2) (1,3,3) (3,3,3) - 2 группы лежат на оси X (x, 1, 3) + (x, 3, 3)

Сортируем по z, x, y
(1,0,2) (1,2,2) (0,1,3) (2,1,3) (1,3,3) (3,3,3) - 1 группа лежит на оси Y (1, y, 2)

Дальше отсеиваете группы по правилам как хотите. Напр если шаг между соседями 1, то ответ "пусто". Просчитав группу запоминаете результат в счетчикаx точки. Расчет по 1 оси не влияет на расчет по другой

@DarthLenin · 23.09.2013, 20:25 **[ТС]**

Что вы понимаете под шагом между соседями? Число координат в которых точки различны? Давайте определим, что сосед порядка d - это точка, которая может быть получена из текущей изменением d координат (неважно на какое число). При этом, при подсчете числа соседей учитываются только точки из данного на входе multiset, но точка относительно которой они считаются может быть произвольной. В этом случае, при d=1 у нас есть 2 точки дающие максимальное число соседей 1 порядка. Это точки 3,1,3 и 1,1,3. Они обе имеют по 3 соседа 1 порядка. Пустое множество вообще не может быть ответом никогда, если входное множество непусто.

@Igor3D · 24.09.2013, 09:52

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

Что вы понимаете под шагом между соседями? Число координат в которых точки различны? Давайте определим, что сосед порядка d - это точка, которая может быть получена из текущей изменением d координат (неважно на какое число).

Я понял координатЫ (именно одной). А оказывается любого числа координат (от 1 до k) но строго на одно число. Напр (0, 0, 0) и (1, 1, 1) - соседи (если d = 1). Также искомая точка может и не входить в исходное множество. Теперь все правильно?

@Qwertiy · 24.09.2013, 10:13

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

Напр (0, 0, 0) и (1, 1, 1) - соседи (если d = 1).

Нет...

@DarthLenin · 24.09.2013, 21:19 **[ТС]**

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

Я понял координатЫ (именно одной). А оказывается любого числа координат (от 1 до k) но строго на одно число. Напр (0, 0, 0) и (1, 1, 1) - соседи (если d = 1). Также искомая точка может и не входить в исходное множество. Теперь все правильно?

Нет, они различаются в трех координатах. Они были бы соседями только при d >= 3
Например, (0, 0, 0) и (0, 0, 500) - соседи при d=1

Новые блоги и статьи Все статьи Все блоги /
Работа с объемным DOM в javascript Htext 04.04.2025 Сегодня прочитал статью тут о расходах памяти в JS, ее утечках и т. п. И вот что вспомнил из своей недавней практики. Может, кому пригодится. Хотя, в той статье об этом тоже есть. Дело в том, что я. . .	Оптимизация производительности Node.js с помощью кластеризации run.dev 04.04.2025 Масштабирование приложений для обработки тысяч и миллионов запросов — обыденная задача для многих команд. Node. js, благодаря своей асинхронной событийно-ориентированной архитектуре, стал популярной. . .	Управление зависимостями в Python с Poetry py-thonny 04.04.2025 Стандартный инструмент для установки пакетов в Python - pip - прекрасно справляется с базовыми сценариями: установил пакет командой pip install и используешь его. Но что произойдёт, когда разные. . .	Мониторинг с Prometheus в PHP Jason-Webb 04.04.2025 Prometheus выделяется среди других систем мониторинга своим подходом к сбору и хранению метрик. В отличие от New Relic, который использует агентный подход и отправляет данные во внешнее хранилище,. . .	Пакет Context в Golang: Управление потоками и ресурсами golander 04.04.2025 Работа с горутинами в Go часто напоминает управление непослушными детьми - они разбегаются кто куда, делают что хотят и не всегда завершаются вовремя. К счастью, в Go 1. 7 появился пакет context,. . .
Контейнеризация React приложений с Docker Reangularity 03.04.2025 Контейнеризация позволяет упаковать приложение со всеми его зависимостями в автономный контейнер, который можно запустить на любой платформе с установленным Docker. Это существенно упрощает процессы. . .	Свой попап в SwiftUI mobDevWorks 03.04.2025 SwiftUI, как декларативный фреймворк от Apple, предоставляет множество инструментов для создания пользовательских интерфейсов. В нашем распоряжении есть такие API как alerts, popovers, action sheets. . .	Антипаттерны микросервисной архитектуры ArchitectMsa 03.04.2025 Хорошо спроектированная микросервисная система может выдержать испытание временем, оставаясь гибкой, масштабируемой и устойчивой к большинству проблем. Такая архитектура обладает высоким уровнем. . .	std::mutex в C++: Советы и примеры использования bytestream 03.04.2025 std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .	Не удержался от оценки концепции двигателя Стирлинга. Hrethgir 03.04.2025 Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .

@DarthLenin 0 / 0 / 0 Регистрация: 22.09.2013 Сообщений: 24

	Найти точку в к-мерном пространстве 22.09.2013, 18:33. Показов 1262. Ответов 19 Метки нет (Все метки) Есть к-мерное дискретное (целочисленное) пространство. В нем отмечены некоторые точки. Нужно найти такую точку, что если через нее провести прямые параллельные базисным векторам, то на них будет лежать максимальное число точек. Если таких несколько, то нужно найти все. Как это можно сделать не перебирая все точки пространства? 0

@dikanev 21 / 21 / 1 Регистрация: 28.05.2010 Сообщений: 67
	22.09.2013, 23:03
	Пусть точек $https://www.cyberforum.ru/cgi-bin/latex.cgi?N$ . Решение в лоб (перебираем все пары точек, увеличиваем счетчик, если ровно одна из координат совпадает, в конце берем точки с максимальным значением счетчика) требует $https://www.cyberforum.ru/cgi-bin/latex.cgi?N^2\cdot k$ сравнений. Чтобы его сократить: 1. Сортируем точки по каждой из координат. Теперь точки у которых совпадает одна из координат лежат рядом в соответствующем массиве. 2. Перебираем точки 2.1. Каждую ищем в отсортированных массивах. 2.2. Составляем список точек, совпадающих по координате с данной. 2.3. Считаем точки, встречающиеся в этом списке ровно один раз. Увеличиваем на эту величину счетчик для текущей точки и на 1 для всех встречающихся один раз точек. 2.4. Удаляем текущую точку из отсортированных массивов. 3. Берем точки с максимальным значением счетчика. Получаем сложность порядка $https://www.cyberforum.ru/cgi-bin/latex.cgi?N\log_{2}N\cdot k$ . 0

@DarthLenin 0 / 0 / 0 Регистрация: 22.09.2013 Сообщений: 24
	23.09.2013, 00:37 [ТС]
	Сообщение от dikanev Пусть точек $https://www.cyberforum.ru/cgi-bin/latex.cgi?N$ . Решение в лоб (перебираем все пары точек, увеличиваем счетчик, если ровно одна из координат совпадает, в конце берем точки с максимальным значением счетчика) Может получиться так, что нужной точки нет в исходном массиве. Пример датасета для 2-мерного пространства: 3,3 1,3 3,3 0,2 2,2 1,3 Ответом здесь будут точки 0,3 и 2,3 Добавлено через 8 минут Замечу, что для 2мерного случая решение несложное, но с обощением на к-мерность возникают проблемы. Например, для 3мерного случая нам придется рассматривать каждую плоскость соответствующую 3ей координате. Собственно вопрос в том, как избежать такого перебора. Кроме того, если ровно одна координата совпадает, то через такие точки нельзя провести прямую параллельную базису. Если ровно одна координата различается, тогда можно. 0

@dikanev 21 / 21 / 1 Регистрация: 28.05.2010 Сообщений: 67
	23.09.2013, 01:15
	Вижу, что я неправильно понял условие задачи и предложил алгоритм для поиска наилучшей точки из отмеченных. Надо еще подумать, но уже поздно. Завтра подумаю. 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	23.09.2013, 11:41
	Имея set <все_точки>, для каждой размерности сохранить map <координата, количество>. Последовательно для каждой пары осей перебираем точку из их map'ов. Полученная точка однозначно оределяет все вектора - считаем для них число точек, проверив дополнительно существует ли точка, которая является пересечением осей. Ассимптотика O(n^4). 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	23.09.2013, 12:25
	Сообщение от Igor3D Я бы сортировал указатели на точки по x, y, z. А ничего что пространство k-мерное, а не 3-мерное? Добавлено через 3 минуты Сообщение от Qwertiy Ассимптотика O(n^4). Наврал. Добавлено через 3 минуты Ассимптотика O(k^3*n^2): k^2 - перебор двух осей n^2 - перебор точек на осях k - подсчёт по оставшимся k-2 осям 0

@DarthLenin 0 / 0 / 0 Регистрация: 22.09.2013 Сообщений: 24
	23.09.2013, 14:19 [ТС]
	Имея set <все_точки> Извиняюсь, я забыл упомянуть, что у нас может быть "несколько точек в одной точке". Так что на входе у нас multiset. И я не слишком понял идею алгоритма. Не могли бы вы поподробнее описать что мы делаем на примере такого датасета: 1,3,3 2,1,3 3,3,3 1,0,2 1,2,2 0,1,3 Добавлено через 24 минуты По сути задачу можно сформулировать так: найти такую точку, чтобы как можно большее число точек, подающихся на вход, отличалось от нее не более чем в 1 координате (на самом деле не более чем в d, но мне хотя бы при d=1 разобраться) 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	23.09.2013, 16:14
	Сообщение от DarthLenin Не могли бы вы поподробнее описать что мы делаем Хм.. Кажется, я бред написал... Думал, что так получится, но тут что-то не то 0

@Igor3D 1916 / 778 / 109 Регистрация: 01.10.2012 Сообщений: 4,365 Записей в блоге: 2
	23.09.2013, 17:17
	Давайте закончим с "первоначальной" постановкой задачи Здесь все ясно: для каждой точки заводим k счетчиков (к - число осей). Сортируя точки k раз заполняем счетчики используя интервал точек сортированного массива отличающихся лишь по одной оси (последний ключ сортировки) Сообщение от DarthLenin По сути задачу можно сформулировать так: найти такую точку, чтобы как можно большее число точек, подающихся на вход, отличалось от нее не более чем в 1 координате (на самом деле не более чем в d, но мне хотя бы при d=1 разобраться) Не слабо... Др словами - "найти точку с максимальной плотностью (d)"? Добавлено через 3 минуты Неясно что имеется ввиду. Напр 2 точки, расстояние между ними по x < 1. но по др оси напр 1000. Такие точки считаются или как? 0

@DarthLenin 0 / 0 / 0 Регистрация: 22.09.2013 Сообщений: 24
	23.09.2013, 17:26 [ТС]
	Сообщение от Igor3D Не слабо... Др словами - "найти точку с максимальной плотностью (d)"? Ну...Не вполне уверен, что я правильно понимаю что такое плотность(d). Точки могут не быть сосредоточены геометрически близко. Но для 3мерного пространства это будет означать при d=1 что мы проводим через точку прямые, при d=2 - плоскости, при d=3 - куб (ну тут уже, очевидно, подойдет любая точка пространства). В общем, по-моему переформулировка получилась более понятной, т.к. она избавляет от геометрического смысла. Добавлено через 4 минуты Сообщение от Igor3D Неясно что имеется ввиду. Напр 2 точки, расстояние между ними по x < 1. но по др оси напр 1000. Такие точки считаются или как? Пространство, как я писал, дискретное. Допускаются только целые координаты. Если точки отличаются только по одной координате, неважно на сколько, то они лежат на одной прямой (параллельной какому-то базисному вектору) и следовательно считаются. Еще раз сформулирую: нужно найти такую точку, чтобы изменением ровно d координат (раз уж упомянул, будем говорить более обощенно, чтобы не путаться), можно было получить как можно больше точек из входного набора 0

@Igor3D 1916 / 778 / 109 Регистрация: 01.10.2012 Сообщений: 4,365 Записей в блоге: 2
	23.09.2013, 17:54
	Сообщение от DarthLenin Еще раз сформулирую: нужно найти такую точку, чтобы изменением ровно d координат (раз уж упомянул, будем говорить более обощенно, чтобы не путаться), можно было получить как можно больше точек из входного набора А что есть "изменение ровно d координат"? Это шаг величиной d по одной из осей? Напр d = 1, точки (5, 5, 1)(5, 5, 2)(5, 5, 3) считаются, каждая точка имеет минимум 2 годных соседей. Тогда кстраивает предыдущее решение. Все это мне напоминпет воксели 0

@DarthLenin 0 / 0 / 0 Регистрация: 22.09.2013 Сообщений: 24
	23.09.2013, 18:02 [ТС]
	Сообщение от Igor3D А что есть "изменение ровно d координат"? Это шаг величиной d по одной из осей? Нет, это шаг произвольной длины по d осям Например, из (5, 5, 1) можно получить (5, 5, 3) изменив одну координату (третью). Тут d=1. Например, между (5,5,1) и (5,3,2) d=2 0

@Igor3D 1916 / 778 / 109 Регистрация: 01.10.2012 Сообщений: 4,365 Записей в блоге: 2
	23.09.2013, 18:14
	Сообщение от DarthLenin Нет, это шаг произвольной длины по d осям Например, из (5, 5, 1) можно получить (5, 5, 3) изменив одну координату (третью). Тут d=1. Например, между (5,5,1) и (5,3,2) d=2 То есть средняя точка имеет минимум 2 соседей, крайние - минимум 1. Все равно устраивает предыдущее решение 0

@DarthLenin 0 / 0 / 0 Регистрация: 22.09.2013 Сообщений: 24
	23.09.2013, 18:22 [ТС]
	Она может иметь больше 2 соседей, может вообще не иметь соседей, главное, чтобы все точки различались ровно в одних и тех же координатах. Например, точки 0,0,1 0,0,2 0,0,3 0,0,4 все являются соседними друг другу т.к. любую из них можно получить изменением 1 координаты в любой другой. Возможно я просто не понимаю то, что вы хотите сказать. Если вы считаете, что ваш алгоритм работает, то не могли бы вы показать конкретные шаги на датасете который я писал выше. Напишу еще раз - 1,3,3 2,1,3 3,3,3 1,0,2 1,2,2 0,1,3. 0

@Igor3D 1916 / 778 / 109 Регистрация: 01.10.2012 Сообщений: 4,365 Записей в блоге: 2
	23.09.2013, 19:46
	(1,3,3) (2,1,3) (3,3,3) (1,0,2) (1,2,2) (0,1,3) Сортируем по x, y, z (0,1,3) (1,0,2) (1,2,2) (1,3,3) (2,1,3) (3,3,3) - никакие 2 точки не лежат на оси Z Сортируем по y, z, x (1,0,2) (0,1,3) (2,1,3) (1,2,2) (1,3,3) (3,3,3) - 2 группы лежат на оси X (x, 1, 3) + (x, 3, 3) Сортируем по z, x, y (1,0,2) (1,2,2) (0,1,3) (2,1,3) (1,3,3) (3,3,3) - 1 группа лежит на оси Y (1, y, 2) Дальше отсеиваете группы по правилам как хотите. Напр если шаг между соседями 1, то ответ "пусто". Просчитав группу запоминаете результат в счетчикаx точки. Расчет по 1 оси не влияет на расчет по другой 0

@DarthLenin 0 / 0 / 0 Регистрация: 22.09.2013 Сообщений: 24
	23.09.2013, 20:25 [ТС]
	Что вы понимаете под шагом между соседями? Число координат в которых точки различны? Давайте определим, что сосед порядка d - это точка, которая может быть получена из текущей изменением d координат (неважно на какое число). При этом, при подсчете числа соседей учитываются только точки из данного на входе multiset, но точка относительно которой они считаются может быть произвольной. В этом случае, при d=1 у нас есть 2 точки дающие максимальное число соседей 1 порядка. Это точки 3,1,3 и 1,1,3. Они обе имеют по 3 соседа 1 порядка. Пустое множество вообще не может быть ответом никогда, если входное множество непусто. 0

@Igor3D 1916 / 778 / 109 Регистрация: 01.10.2012 Сообщений: 4,365 Записей в блоге: 2
	24.09.2013, 09:52
	Сообщение от DarthLenin Что вы понимаете под шагом между соседями? Число координат в которых точки различны? Давайте определим, что сосед порядка d - это точка, которая может быть получена из текущей изменением d координат (неважно на какое число). Я понял координатЫ (именно одной). А оказывается любого числа координат (от 1 до k) но строго на одно число. Напр (0, 0, 0) и (1, 1, 1) - соседи (если d = 1). Также искомая точка может и не входить в исходное множество. Теперь все правильно? 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	24.09.2013, 10:13
	Сообщение от Igor3D Напр (0, 0, 0) и (1, 1, 1) - соседи (если d = 1). Нет... 0

@DarthLenin 0 / 0 / 0 Регистрация: 22.09.2013 Сообщений: 24
	24.09.2013, 21:19 [ТС]
	Сообщение от Igor3D Я понял координатЫ (именно одной). А оказывается любого числа координат (от 1 до k) но строго на одно число. Напр (0, 0, 0) и (1, 1, 1) - соседи (если d = 1). Также искомая точка может и не входить в исходное множество. Теперь все правильно? Нет, они различаются в трех координатах. Они были бы соседями только при d >= 3 Например, (0, 0, 0) и (0, 0, 500) - соседи при d=1 0