Задачка про города

[ИС]

Дана координатная плоскость. Ось OX представляет собой
железную дорогу, в целочисленных точках которой можно
построить жд-станцию (x,0). В некоторых других точках
плоскости с целочисленными координатами находятся
населенные пункты. Их может быть больше 1000000, и их
координаты вводятся из стандартного ввода в виде:
x1,y1
x2,y2
......
xn,yn

Требуется найти координаты станции такой, чтобы
максимальное расстояние между ней и населенными пунктами
было бы минимальным (другими словами, для каждой
возможной станции рассматриваются расстояния до всех
посёлков, и из них берется максимальное. У искомой
станции должно быть минимальное из этих максимальных).


Как бы похитрее эту задачку решить. Кроме тупого перебора в голову пока ничего не приходит =(

-- Чт окт 15, 2009 13:01:20 --

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

[ИСН]

Покрутите в голове слова "выпуклая оболочка".

[ИС]

А я не знаю что это )
Задачка должна решаться только знаниями из школьного курса...

[worm2]

ИС в сообщении #251860 писал(а):

А я не знаю что это )
Задачка должна решаться только знаниями из школьного курса...

Ну, это вполне себе школьное понятие (для школьных олимпиадных задач по программированию). Это такая выпуклая фигура (минимально возможная), что все точки лежат внутри неё, или на границе.

[gris]

Порешайте задачу вручную для 2 станций, потом для трёх, потом и озарение наступит.

[ИС]

Чет не озаряет меня седня (
подскажите плиз еще что-нибудь

[PAV]

Читайте здесь:

выпуклая оболочка и алгоритмы ее построения

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

Поэтому если построить ее, то все остальные пункты можно выкинуть, и это при удачном стечении обстоятельств может сократить перебор.

[ИС]

PAV
Точняк! спасибо!

[ИС]

А какую структуру данный тут лучше использвоать для хранения координат городов?

[Cave]

Выпуклая оболочка здесь совершенно не по делу, если исходное множество точек лежит в вершинах выпуклого многоугольника, то она не отсечёт ни одной точки.
Про координаты что сказано кроме того, что они целочисленные? Ограничения на $x,y$ есть? Какое точное ограничение на число городов?

[ИСН]

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

[Cave]

Очевидно, что это не учебная, а олимпиадная задача, и в них нужно задачи решать целиком. Если олимпиада командная, то только такие задачи засчитываются (то есть если ответ программы не совпал хотя бы на одном, даже самом большой и сложном тесте с авторским, то она признаётся неработающей); если это тренировка, то нужно учиться решать задачи целиком, а не придумывать эвристики. И только если человек находится на индивидуальной олимпиаде и не смог сообразить, как решить задачу в общем случае, имеет смысл писать какое-нибудь частичное решение, которое проходит часть тестов.
Поэтому будем решать до конца задачу.

[ИС]

Запнулся на такой штуке.
В сканирование по Грехому. Нужно упорядочить точки $(p_1, ... p_m)$ по возрастанию полярного угла относительно точки $ p_0$.

Как найти полярный угол точки $p_i$ относительно $p_0$?
Его искать из формулы скалярного произведения вектора $\overline{p_0 p_i}$ и вектора {1,0} ?
Можно это сделать как-нибудь хитрее?

[venco]

ИС в сообщении #264152 писал(а):

Запнулся на такой штуке.
В сканирование по Грехому. Нужно упорядочить точки $(p_1, ... p_m)$ по возрастанию полярного угла относительно точки $ p_0$.

Как найти полярный угол точки $p_i$ относительно $p_0$?

Если $p_i$ заданы как комплексные переменные, то:

1. double angle = arg(p[i]-p[0]); 

Если как координаты, то:

1. double angle = atan2(y[i]-y[0], x[i]-x[0]); 

ИС в сообщении #264152 писал(а):

Его искать из формулы скалярного произведения вектора $\overline{p_0 p_i}$ и вектора {1,0} ?
Можно это сделать как-нибудь хитрее?

Можно и похитрее, избежав медленных операций типа арктангенса. Только произведение нужно векторное, и код будет сложнее.
Знак векторного произведения показывает, справа или слева находится другой вектор. К сожалению, круг у нас замкнут, поэтому надо сначала разбить все точки на две половины относительно, например, оси X, а потом каждую половину отсортировать используя знак векторного произведения как оператор сравнения.
Ещё надо будет учесть возможность совпадения углов. Полностью сейчас писать лень.

[Maslov]

ИС в сообщении #264152 писал(а):

Его искать из формулы скалярного произведения вектора $\overline{p_0 p_i}$ и вектора {1,0} ?
Можно это сделать как-нибудь хитрее?

Вот здесь почитайте: Препарата, Шеймос. Вычислительная геометрия. Введение. (3.3. Алгоритм построения выпуклой оболочки на плоскости.)