2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3
 
 Re: Задачка про города
Сообщение28.11.2009, 07:08 
Минимальный круг проходит либо через город слева по дороге, либо через город справа, либо через оба (город ровно напротив станции будем считать находящимся и слева, и справа).
Если минимальный круг проходит через город слева (или напротив), то при смещении станции направо круг обязательно увеличится, так как он должен продолжать охватывать этот город на границе, а расстояние до него увеличится. При этом города, находящиеся справа, строго приблизятся, т.е. не смогут оказаться на границе, пока они справа. Таким образом, если в каком-то положении станции граница минимального круга проходит через город слева (напротив), то во всех положениях станции правее граница также будет определятся городами слева, а значит, так и будет увеличиваться.
Аналогично, если круг проходит через город справа (напротив), то при смещении станции налево во-первых, минимальный круг увеличится, во-вторых, так и будет продолжатся увеличиваться при дальнейшем смещении станции налево.
Таким образом, минимум строго один, и достигается в таком положении станции, что либо граница проходит через два города по разные стороны в направлении дороги, либо через город строго напротив станции.

 
 
 
 Re: Задачка про города
Сообщение28.11.2009, 16:47 
Извините, я дальше не читал, сразу не понял, что такое города слева и справа по дороге. Поясните, пожалуйста.

 
 
 
 Re: Задачка про города
Сообщение28.11.2009, 16:57 
Если координаты станции - $(x_s,0)$, то "слева" - это все точки с координатой $x<x_s$, а "справа" - с координатой $x>x_s$. "Напротив" - с координатой $x=x_s$. Координата $y$ - любая.

 
 
 
 Re: Задачка про города
Сообщение28.11.2009, 17:53 
Спасибо. Выглядит всё правдоподобно.
Сложность в таком случае получается $O(N\log C)$, где $N$ - число городов, а $C$ - максимум модуля $x$-координат городов.

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


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