С++ алгоритм пересечения и объединения множеств

lixe, 464 просмотра

Задача:
Заданы два множества точек на плоскости. Построить пересечение и разность этих множеств.
При этом множество точек плоскости задать своими координатами в виде двух динамических массивов x[n] и y[n], где (xi, yi ) — координаты i-й точки.
Просьба подсказать хотя бы алгоритм.

Примечание:
Сортировать,естественно нельзя,тк связь между координатами нарушится.

Ответы:

> При этом множество точек плоскости задать своими координатами в виде двух динамических массивов x[n] и y[n], где (xi, yi ) — координаты i-й точки.
Идиотское условие!

Shpectator

ну это просто, берешь первое множество, и про каждую точку проверяешь если есть такая во втором множесте. Если есть, отправляешь ее в группу "Пересечение".
А разность, имеется ввиду, точки которые находится только в одном множестве, но не в обоих?
Тогда в "Разность" отправляешь остальные точки из первого множества, а потом запускаешь проверку на второе множество, и тоже отправляешь в "Разность" те точки, которые не находятся в первом множестве. Пересечение тут искать не надо, т.к. достаточно проверить все точки из первого множества, потому что эти точки находятся в обоих группах, а разность надо проверить и на второй группе, т.к. есть точки которые находятся в первой, но не во второй,и наоборот.

Just another one user

Ну если показать хотя бы алгоритм, то

Lockal

Если это массив, то при чём тут c++? Это всё на си делается.
Вариант реализации в лоб: в цикле от 0 до n обходим все точки одного множества. При обходе проверяем, есть ли точка с такими координатами в мн-ве 2. Сложность n^2. За такое решение могут дать в лоб.

14 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.