Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
киракира
0 / 0 / 0
Регистрация: 03.04.2012
Сообщений: 14
#1

несколько точек на плоскости - C++

10.04.2012, 11:04. Просмотров 531. Ответов 1
Метки нет (Все метки)

Дано несколько точек на плоскости с целыми координатами. Определить центр симметрии этого множества точек, если он существует
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.04.2012, 11:04     несколько точек на плоскости
Посмотрите здесь:

C++ Дано n точек на плоскости
C++ В заданном множестве точек плоскости найти количество точек в каждой из четвертей
C++ Дано несколько точек с целочисленными координатами. Определить максимальное количество точек из них, лежащих на одной прямой. Если можно напечатать н
C++ Множества точек на плоскости
C++ Множество точек на плоскости
C++ Поиск точек на плоскости
Дано множество точек на плоскости C++
C++ Дано множество точек на плоскости, заданных полярными координатами. Получить декартовы координаты этих точек
C++ Среди заданных точек на плоскости найти ту, у которой расстояние суммы равно наибольшему от остальных точек
C++ В заданном множестве точек плоскости найти количество точек в каждой из четвертей
Из множества точек на плоскости найти точки, образующие параллелограмм с наибольшим количеством точек внутри C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
10.04.2012, 14:24     несколько точек на плоскости #2
Если центр симметрии существует, то он должен быть находиться в середине отрезка, соединяющего некую пару точек из этого множества. То есть на самом деле все точки должны делиться на пары, у каждой пары должен быть один и тот же центр симметрии.
Еще вариант - в центре симметрии тоже может находиться точка.

Поэтому алгоритм такой
1) Перебираем все пары несовпадающих точек
Пусть мы взяли точки A и B из множества
Определяем точку C - середина отрезка A,B ( С - это будет центр симметрии )
3) Помечаем точки A,B флагом
Если у нас есть точка С в множестве, то тоже помечаем ее флагом
4) Перебираем все точки не помеченные флагом
Пусть мы взяли точку D
Для точки D ищем точку, симметричную ей точку E относительно C
Если точки E не найдено - значит этот вариант центра симметрии C отпадает и мы переходим на 1
Если мы нашли точку E - значит помечаем точки D,E флагом и переходим на 4
5) Если в итоге все точки помечены флагом
значит точка C - это искомый центр симметрии и задаче решена
6) Если в результате перебора в 1 мы не нашли центр симметрии
то значит центр симметрии не существует

Добавлено через 3 минуты
Не смотря на то что все точки имеют целые координаты
все равно центр симметрии может иметь не целые координаты
Поэтому рекомендую все вычисления проводить в double x,y
И для сравнения координат использовать фиксированную точность EPS, например 0.00001
Yandex
Объявления
10.04.2012, 14:24     несколько точек на плоскости
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru