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

@freewrestler · Регистрация: 10.11.2011

Author24 — интернет-сервис помощи студентам

Уважаемые форумчане помогите пожалуйста со следующей задачкой:
Даны n (1 <= n <= 10^5) попарно различных точек на плоскости с целыми координатами до 10^6 по абсолютной величине. Найдите среди них две точки A и B такие, что угол AOB минимальный. O - центр координат.

@~~IrineK~~ · 11.04.2014, 00:09

Сообщение от freewrestler

Даны n (1 <= n <= 10^5) попарно различных точек

Может, все таки 2 <= n <= 10^5?

@freewrestler · 11.04.2014, 00:40 **[ТС]**

нет, 1 <= n т.к если n = 1, то значит 1 пара точек, т.е 2 точки.

@~~IrineK~~ · 11.04.2014, 00:50

Если n - это количество пар, то сколько же у вас точек?

@freewrestler · 11.04.2014, 00:59 **[ТС]**

Даны n попарно различных точек - я так понял, что тут имеется в виду "n пар" точек, если например n = 5, то точек 10. А если я неправильно понял условие, то подскажите пожалуйста.

@~~IrineK~~ · 11.04.2014, 03:37

Я поняла так, что дано n точек, и если взять любые две из них, то они различны.
Т.е., в конечном счете они все различны.

В этом смысле точек не может быть меньше двух.

@freewrestler · 11.04.2014, 04:40 **[ТС]**

Да, вы правы, я ошибся в понимании условии. И соответственно ограничениями для n будут 1 <= n <= 10 ^ 5

@~~IrineK~~ · 11.04.2014, 06:13

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

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

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

Добавлено через 1 час 20 минут
Поправка:
Миллион точек упорядочивать не будем, а просто берем каждую и по отношению к ней проверяем на ближайшую "левую".

@freewrestler · 11.04.2014, 23:28 **[ТС]**

"Координаты целочисленные, что намекает на использование соответствующих методов." не могли бы вы мне скинуть ссылку на материал, чтобы я его прочитал или же вкратце объяснить мне этот метод

Добавлено через 5 часов 3 минуты
Спасибо, догадался)

@Dani · 12.04.2014, 00:02

Сообщение от IrineK

Миллион точек упорядочивать не будем, а просто берем каждую и по отношению к ней проверяем на ближайшую "левую".

А как это сделать?

Можно упорядочить сортировкой быстрой, по углу. И нормально будет.

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126
		1
	Найдите среди точек две такие, что угол AOB минимальный 10.04.2014, 23:29. Показов 628. Ответов 9 Метки нет (Все метки) Уважаемые форумчане помогите пожалуйста со следующей задачкой: Даны n (1 <= n <= 10^5) попарно различных точек на плоскости с целыми координатами до 10^6 по абсолютной величине. Найдите среди них две точки A и B такие, что угол AOB минимальный. O - центр координат. 0

@~~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 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	12.04.2014, 00:02	10
	Сообщение от IrineK Миллион точек упорядочивать не будем, а просто берем каждую и по отношению к ней проверяем на ближайшую "левую". А как это сделать? Можно упорядочить сортировкой быстрой, по углу. И нормально будет. 0

Опции темы