Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

Дано целое число N. Найдите все такие целые числа d, что N делится на d2 и не делится на d3. - C++
Вроде все норм работает, по крайней мере числа находит, но почему-то если ввожу большие числа, моя винда пишет сообщение о ошибке. Надеюсь...

Верно ли, что среди точек есть хотя бы одна, принадлежащая квадрату? - C++
Дано натуральное n, действительные x_1, y_1, ... x_n, y_n Выяснить, верно ли, что среди точек (x_i, y_i), i=1, ..., n есть хотя бы ...

Найти среди двузначных чисел такие, что квадрат числа равен кубу суммы цифр этого числа - C++
Найти среди двузначных чисел такие, что квадрат числа равен кубу суммы цифр этого числа. Помогите пожалуйста, как тут написать само...

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

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

Матрица D(4,4). Определить максимальный среди положительных, минимальный среди отрицательных и поменять их местами - C++
Помогите решить задачу: Задана матрица D(4,4). Определить максимальный среди положительных, минимальный среди отрицательных и поменять их...

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

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

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

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

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

Добавлено через 5 часов 3 минуты
Спасибо, догадался)
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,291
Записей в блоге: 2
Завершенные тесты: 1
12.04.2014, 00:02 #10
Цитата Сообщение от IrineK Посмотреть сообщение
Миллион точек упорядочивать не будем, а просто берем каждую и по отношению к ней проверяем на ближайшую "левую".
А как это сделать?

Можно упорядочить сортировкой быстрой, по углу. И нормально будет.
0
12.04.2014, 00:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.04.2014, 00:02
Привет! Вот еще темы с ответами:

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

Из точек на плоскости выбрать две такие, чтобы разность количества точек, лежащих по разные стороны от прямой, была мин. - Turbo Pascal
Из заданного множества точек на плоскости выбрать две различные точки так, чтобы количества точек, лежащих по разные стороны прямой,...

Среди множества точек на плоскости найдите пару точек с минимальным расстоянием между ними - Pascal
Среди множества точек на плоскости найдите пару точек с минимальным расстоянием между ними. Определение расстояния между двумя точками...

Через две точки проведен отрезок прямой. Найти среди заданных трех точек такую, что также относится к этому отрезку - C (СИ)
Собственно сама задача. Через две точки проведен отрезок прямой. Найти среди заданных трех точек такую, что также относится к этому...


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

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