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

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

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

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

10.04.2014, 23:29. Просмотров 242. Ответов 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++
Дано натуральное n, действительные x_1, y_1, ... x_n, y_n Выяснить, верно ли, что среди точек (x_i, y_i), i=1, ..., n есть хотя бы ...

Среди введенных четных чисел найдите максимум (М1), также найдите максимум (М2) среди нечетных чисел - C++
На вычислительной практие дали такое задание: С клавиатуры вводится произвольная последовательность целых положительных чисел. Числа...

Сортировать массив, чтобы минимальный искался среди четных элементов, а максимальный - среди нечетных - C++
Сортировать массив, чтобы минимальный искался среди четных элементов, а максимальный - среди нечетных. Помогите плз Очень срочно ...

Есть ли среди чисел в диапазоне от А до В такие, произведение цифр которых равно С? - C++
1. Написать программу на языке С++ для решения задачи: Даны два числа А, В и С. Определить, есть ли среди чисел в диапазоне от А до В...

Символьные строки (верно ли, что существуют такие натуральные i и j, что 1 < i < j < n и что si совпадает с s(i+1), а sj совпадает с s(j+1)) - C++
Даны символы s1, s2, … Известно, что символ s1 отличен от восклицательного знака и что среди s2, s3,. .. есть по крайней мере один ...

Определить, есть ли среди элементов массива такие, которые равны сумме двух других - C++
Дано натуральное число n и целые числа a(1), a(2), ..a(n) (n&lt;100). Определить, есть ли среди этих чисел такие, которые равны сумме двух...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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 минимальный
Еще ссылки по теме:

Среди чисел от 1 до n найти такие, запись которых совпадает с последними цифрами записи их квадратов - C++
Дано натуральное число п. Среди чисел 1,..., п найти такие, запись которых совпадает с последними цифрами записи их квадратов ...

Переставляя строки и столбцы матрицы, перенести ее минимальный элемент в левый верхний угол - C++
Тема: Функции2. 9. Пусть дано матрицу nxm, заполненную псевдослучайными числами в заданном диапазоне. Переставляя строки и столбцы,...

Среди заданных натуральных чисел найти такие, десятичная запись которых не содержит одинаковых цифр - C++
Среди заданных натуральных чисел найти такие, десятичная запись которых не содержит одинаковых цифр. По идее есть работающий код, но...

Среди заданных натуральных чисел найти такие, десятичная запись которых не содержит одинаковых цифр - C++
Задание: Среди заданных натуральных чисел найти такие, десятичная запись кото- рых не содержит одинаковых цифр. я понимаю, что и...


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

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

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

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