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

Круг и прямая - C++

Восстановить пароль Регистрация
 
Lel'ka
8 / 8 / 2
Регистрация: 10.07.2012
Сообщений: 38
11.07.2012, 13:27     Круг и прямая #1
Дорогие форумчане! Не откажите в помощи, если есть идеи по заданию. Алгоритм или небольшая помощь с кодом

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

Заранее спасибо!))
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2012, 13:27     Круг и прямая
Посмотрите здесь:

Прямая и окружность C++
Квадрат и прямая C++
Окружность и прямая C++
Параллельная прямая C++
Создайте структуру Прямая C++
C++ Структуры (Создайте структуру Прямая с элементами x1, y1, x2, y2 – координаты двух точек, через которые проходит прямая)
Прямая линия на плоскости C++
C++ Круг, множество точек, прямая проходящая через две точки и через центр круга

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
12.07.2012, 08:34     Круг и прямая #2
извольте...

Добавлено через 7 минут
очевидно, Вам необходимо найти прямую, проходящую через некоторые две точки множества М, такую, что она максимально похожа на диаметр круга.
чуть подробнее. перебираем все пары точек... обозначим р1, р2 - выбранная пара точек, с - центр круга. для каждой пары точек строим диаметры - прямые проходящие через р1-с и р2-с соответственно. Ваша задача, перебрав все пары точек, найти такую пару, что прямая, проходящая через них наиболее похожа на диаметр... как понять, насколько прямая похожа на диаметр...? Вам всего лишь нужно найти прямую, которая имеет наименьший угол с диаметром. как найти угол между прямыми, проходящими чрез одну точку, разберетесь сами. ах, да... еще нужно вывести ответ...)

Добавлено через 5 минут
совсем забыл... тупой перебор будет выполнять примерно M^2, Вам следует немного подумать и уменьшить это количество до M^2\2... достаточно тривиальная оптимизация.
Yandex
Объявления
12.07.2012, 08:34     Круг и прямая
Ответ Создать тему
Опции темы

Текущее время: 03:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru