2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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


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

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

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

 
 
 
 Re: Задачка про города
Сообщение15.10.2009, 12:17 
Аватара пользователя
Покрутите в голове слова "выпуклая оболочка".

 
 
 
 Re: Задачка про города
Сообщение15.10.2009, 12:45 
Аватара пользователя
А я не знаю что это )
Задачка должна решаться только знаниями из школьного курса...

 
 
 
 Re: Задачка про города
Сообщение15.10.2009, 13:10 
Аватара пользователя
ИС в сообщении #251860 писал(а):
А я не знаю что это )
Задачка должна решаться только знаниями из школьного курса...

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

 
 
 
 Re: Задачка про города
Сообщение15.10.2009, 15:29 
Аватара пользователя
Порешайте задачу вручную для 2 станций, потом для трёх, потом и озарение наступит.

 
 
 
 Re: Задачка про города
Сообщение15.10.2009, 22:02 
Аватара пользователя
Чет не озаряет меня седня (
подскажите плиз еще что-нибудь :wink:

 
 
 
 Re: Задачка про города
Сообщение15.10.2009, 22:19 
Аватара пользователя
Читайте здесь:

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

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

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

 
 
 
 Re: Задачка про города
Сообщение16.10.2009, 00:09 
Аватара пользователя
PAV
Точняк! спасибо! :P

 
 
 
 Re: Задачка про города
Сообщение16.11.2009, 15:06 
Аватара пользователя
А какую структуру данный тут лучше использвоать для хранения координат городов?

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

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

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

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

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

 
 
 
 Re: Задачка про города
Сообщение21.11.2009, 17:51 
ИС в сообщении #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, а потом каждую половину отсортировать используя знак векторного произведения как оператор сравнения.
Ещё надо будет учесть возможность совпадения углов. Полностью сейчас писать лень.

 
 
 
 Re: Задачка про города
Сообщение21.11.2009, 17:54 
ИС в сообщении #264152 писал(а):
Его искать из формулы скалярного произведения вектора $\overline{p_0 p_i}$ и вектора {1,0} ?
Можно это сделать как-нибудь хитрее?
Вот здесь почитайте: Препарата, Шеймос. Вычислительная геометрия. Введение. (3.3. Алгоритм построения выпуклой оболочки на плоскости.)

 
 
 [ Сообщений: 34 ]  На страницу 1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group