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

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

Войти
Регистрация
Восстановить пароль
 
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
#1

Найдите среди точек две такие, что угол AOB минимальный - C++

10.04.2014, 23:29. Просмотров 233. Ответов 9
Метки нет (Все метки)

Уважаемые форумчане помогите пожалуйста со следующей задачкой:
Даны n (1 <= n <= 10^5) попарно различных точек на плоскости с целыми координатами до 10^6 по абсолютной величине. Найдите среди них две точки A и B такие, что угол AOB минимальный. O - центр координат.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.04.2014, 23:29     Найдите среди точек две такие, что угол AOB минимальный
Посмотрите здесь:

Верно ли, что среди точек есть хотя бы одна, принадлежащая квадрату? C++
C++ Дано целое число N. Найдите все такие целые числа d, что N делится на d2 и не делится на d3.
C++ Из заданного на плоскости множества точек выбрать такие три, которые составляют треугольник наибольшего периметра.
C++ Определить, есть ли среди элементов массива такие, которые равны сумме двух других
C++ есть ли среди чисел в диапазоне от А до В такие, произведение цифр которых равно С.
C++ Символьные строки (верно ли, что существуют такие натуральные i и j, что 1 < i < j < n и что si совпадает с s(i+1), а sj совпадает с s(j+1))
Найти среди двузначных чисел такие, что квадрат числа равен кубу суммы цифр этого числа C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IrineK
Заблокирован
11.04.2014, 00:09     Найдите среди точек две такие, что угол AOB минимальный #2
Цитата Сообщение от freewrestler Посмотреть сообщение
Даны n (1 <= n <= 10^5) попарно различных точек
Может, все таки 2 <= n <= 10^5?
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
11.04.2014, 00:40  [ТС]     Найдите среди точек две такие, что угол AOB минимальный #3
нет, 1 <= n т.к если n = 1, то значит 1 пара точек, т.е 2 точки.
IrineK
Заблокирован
11.04.2014, 00:50     Найдите среди точек две такие, что угол AOB минимальный #4
Если n - это количество пар, то сколько же у вас точек?
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
11.04.2014, 00:59  [ТС]     Найдите среди точек две такие, что угол AOB минимальный #5
Даны n попарно различных точек - я так понял, что тут имеется в виду "n пар" точек, если например n = 5, то точек 10. А если я неправильно понял условие, то подскажите пожалуйста.
IrineK
Заблокирован
11.04.2014, 03:37     Найдите среди точек две такие, что угол AOB минимальный #6
Я поняла так, что дано n точек, и если взять любые две из них, то они различны.
Т.е., в конечном счете они все различны.

В этом смысле точек не может быть меньше двух.
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
11.04.2014, 04:40  [ТС]     Найдите среди точек две такие, что угол AOB минимальный #7
Да, вы правы, я ошибся в понимании условии. И соответственно ограничениями для n будут 1 <= n <= 10 ^ 5
IrineK
Заблокирован
11.04.2014, 06:13     Найдите среди точек две такие, что угол AOB минимальный #8
Ну бог с ним, с одной точкой. В конце концов, в этом случае сразу переходим на "Нет решений, поскольку нет угла".

Общая идея такая:
1) Ваши точки неупорядочены по часовой или против часовой стрелки? Тогда нужно это сделать.
2) После этого - обходим и меряем углы соседей.
3) Делаем вывод.

Координаты целочисленные, что намекает на использование соответствующих методов.

Добавлено через 1 час 20 минут
Поправка:
Миллион точек упорядочивать не будем, а просто берем каждую и по отношению к ней проверяем на ближайшую "левую".
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
11.04.2014, 23:28  [ТС]     Найдите среди точек две такие, что угол AOB минимальный #9
"Координаты целочисленные, что намекает на использование соответствующих методов." не могли бы вы мне скинуть ссылку на материал, чтобы я его прочитал или же вкратце объяснить мне этот метод

Добавлено через 5 часов 3 минуты
Спасибо, догадался)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.04.2014, 00:02     Найдите среди точек две такие, что угол AOB минимальный
Еще ссылки по теме:

C++ Среди заданных точек на плоскости найти ту, у которой расстояние суммы равно наибольшему от остальных точек
C++ Матрица D(4,4). Определить максимальный среди положительных, минимальный среди отрицательных и поменять их местами
Среди введенных четных чисел найдите максимум (М1), также найдите максимум (М2) среди нечетных чисел C++
C++ Среди чисел от 1 до n найти такие, запись которых совпадает с последними цифрами записи их квадратов
C++ Найти заданный угол треугольника, зная две его стороны и периметр

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

Или воспользуйтесь поиском по форуму:
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
12.04.2014, 00:02     Найдите среди точек две такие, что угол AOB минимальный #10
Цитата Сообщение от IrineK Посмотреть сообщение
Миллион точек упорядочивать не будем, а просто берем каждую и по отношению к ней проверяем на ближайшую "левую".
А как это сделать?

Можно упорядочить сортировкой быстрой, по углу. И нормально будет.
Yandex
Объявления
12.04.2014, 00:02     Найдите среди точек две такие, что угол AOB минимальный
Ответ Создать тему
Опции темы

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