Задний план

Вы богатый руководитель империи программного обеспечения. Ваше время стоит много денег. Таким образом, вы всегда должны путешествовать по максимально эффективному маршруту. Однако, как руководитель, вы проводите много времени, участвуя в важных телефонных звонках. Крайне важно, чтобы вы никогда не сбрасывали вызовы, поэтому вы никогда не должны путешествовать через районы, где нет сотовой связи!

Соревнование

Вам будет предоставлен список из трех кортежей, каждый из которых представляет местоположение и мощность вышки сотовой связи. В качестве примера, [50, 25, 16]представлял бы вышку сотовой связи, расположенную по <x,y> = <50, 25>кругу с радиусом 16, представляющим ее круг влияния. Имея в виду этот список, вы должны путешествовать из стартовой позиции в <0, 0>пункт назначения <511, 511>в кратчайшее возможное расстояние без потери услуги сотовой связи. Это код-гольф , поэтому выигрывает самый короткий код!

Ввод, вывод

Вы можете свободно манипулировать вводом в форме, которая облегчает его чтение, например в файле или в виде вложенного массива, с помощью STDIN evalи т. Д. Вы можете жестко закодировать ввод, если ваш код работает для других входов, как Что ж. Точные символы, используемые для жесткого кодирования ввода, не будут учитываться, но будут указаны имя переменной и символы назначения. Не следует предполагать, что входные данные находятся в каком-либо определенном порядке или что каждая вышка сотовой связи имеет отношение к проблеме. Если у вас есть какие-либо вопросы, пожалуйста, оставьте комментарий, и я постараюсь уточнить его.

Выходными данными должен быть список координат, отмечающий точки, которые при подключении по порядку образуют путь к выходу. Точность нужно только округлить до ближайшего целого числа, и если вы на 1-2 единицы от того, что у меня есть в выходном примере, это нормально. Я включил изображения ниже, чтобы прояснить это.

Удачи!

Примеры

input:
[ 32,  42,  64]
[112,  99,  59]
[141, 171,  34]
[157, 191,  28]
[177, 187,  35]
[244, 168,  57]
[289, 119,  20]
[299, 112,  27]
[354,  59,  58]
[402,  98,  23]
[429,  96,  29]
[424, 145,  34]
[435, 146,  20]
[455, 204,  57]
[430, 283,  37]
[432, 306,  48]
[445, 349,  52]
[424, 409,  59]
[507, 468,  64]

output:
0 0
154 139
169 152
189 153
325 110
381 110
400 120
511 511

input2
[ 32,  42,  64]
[112,  99,  59]
[141, 171,  34]
[157, 191,  28]
[177, 187,  35]
[244, 168,  57]
[289, 119,  20]
[299, 112,  27]
[354,  59,  58]
[402,  98,  23]
[429,  96,  29]
[424, 145,  34]
[435, 146,  20]
[455, 204,  57]
[430, 283,  37]
[432, 306,  48]
[445, 349,  52]
[424, 409,  59]
[507, 468,  64]
[180, 230,  39]
[162, 231,  39]
[157, 281,  23]
[189, 301,  53]
[216, 308,  27]
[213, 317,  35]
[219, 362,  61]
[242, 365,  42]
[288, 374,  64]
[314, 390,  53]
[378, 377,  30]
[393, 386,  34]

output2:
0 0
247 308
511 511

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

Python, 1,291 1,271 1225 байт

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

В качестве резиновой ленты мы можем выбрать любой путь P между двумя конечными точками, который проходит внутри замкнутой области. Затем мы можем вызвать решение задачи о резиновой полосе, чтобы получить (локально) минимальный путь. Задача, конечно, состоит в том, чтобы найти такой путь P или, точнее, найти достаточно путей, чтобы по крайней мере один из них создал глобально минимальный путь (обратите внимание, что в первом тестовом примере нам нужен по крайней мере один путь к охватить все возможности, а во втором тестовом случае - как минимум два.)

Наивным подходом было бы просто попробовать все возможные пути: для каждой последовательности соседних (т. Е. Пересекающихся) окружностей, которая соединяет две конечные точки, выбирайте путь вдоль их центров (когда две окружности пересекаются, отрезок между их центрами всегда находится в их объединении .) Хотя этот подход технически верен, он может привести к смехотворно большому количеству путей. Хотя я смог решить первый тестовый пример с использованием этого подхода в течение нескольких секунд, второй занял вечность. Тем не менее, мы можем взять этот метод в качестве отправной точки и попытаться свести к минимуму количество путей, которые мы должны проверить. Это то, что следует.

Мы строим наши пути, в основном выполняя поиск в глубину на графике окружностей. Мы ищем способ устранения потенциальных направлений поиска на каждом этапе поиска.

Предположим, что в какой-то момент мы находимся в окружности A , которая имеет две соседние окружности B и C , которые также соседствуют друг с другом. Мы можем добраться от A до C , посетив B (и наоборот), поэтому мы можем подумать, что посещать B и C напрямую из A не нужно. К сожалению, это неправильно, как показано на рисунке:

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

Как насчет этого: если мы тестируем оба хода A → B и A → C , то нет необходимости проверять A → B → C или A → C → B , поскольку они не могут привести к более коротким путям. Опять неправильно:

Дело в том, что использование аргументов, основанных исключительно на смежности, не приведет к его сокращению; мы также должны использовать геометрию задачи. Общим для двух приведенных выше примеров (а также для второго контрольного примера в большем масштабе) является то, что в замкнутой области есть «дыра». Это проявляется в том, что некоторые точки пересечения на границе - наши «гвозди» - находятся внутри треугольника △ ABC , вершинами которого являются центры окружностей:

Когда это происходит, есть вероятность, что переход от А к В и от А к С приведет к различным путям. Что еще более важно, когда это не происходит (то есть, если не было промежутка между A , B и C ), тогда гарантируется, что все пути, начинающиеся с A → B → C и с A → C и которые в противном случае эквивалентны, приведут в том же локально минимального пути, следовательно , если мы посещаем B мы не должны также посетить C непосредственно из A .

Это приводит нас к нашему методу исключения: когда мы находимся в круге A , мы сохраняем список H соседних кругов, которые мы посетили. Этот список изначально пуст. Мы посетить соседний круг B , если существуют какие - либо «гвозди» в всех треугольников , образованных центрами A , B и любого из кругов H , прилегающих к B . Этот метод значительно снижает количество проверяемых путей до 1 в первом тестовом примере и 10 во втором.

Еще несколько заметок:

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

• Я использовал алгоритм от моего решения проблемы резинкой. Поскольку этот алгоритм является инкрементным, его довольно легко интегрировать в процесс поиска пути, поэтому мы минимизируем путь по мере продвижения. Поскольку многие пути совместно используют начальный сегмент, это может значительно улучшить производительность, когда у нас много путей. Это также может снизить производительность, если тупиков гораздо больше, чем допустимых путей. В любом случае, для данных тестов достаточно хорошо выполнить алгоритм для каждого пути в отдельности.

• Существует один крайний случай, когда это решение может потерпеть неудачу: если любая из точек на границе является точкой пересечения двух касательных окружностей, то при некоторых условиях результат может быть неправильным. Это связано с тем, как работает алгоритм резиновой ленты. С некоторыми модификациями можно обрабатывать и эти случаи, но, черт возьми, это уже достаточно долго.

# First test case
I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.)}
# Second test case
#I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.),((180.,230.),39.),((162.,231.),39.),((157.,281.),23.),((189.,301.),53.),((216.,308.),27.),((213.,317.),35.),((219.,362.),61.),((242.,365.),42.),((288.,374.),64.),((314.,390.),53.),((378.,377.),30.),((393.,386.),34.)}

from numpy import*
V=array;X=lambda u,v:u[0]*v[1]-u[1]*v[0];L=lambda v:dot(v,v)
e=V([511]*2)
N=set()
for c,r in I:
 for C,R in I:
  v=V(C)-c;d=L(v)
  if d:
    a=(r*r-R*R+d)/2/d;q=r*r/d-a*a
    if q>=0:w=V(c)+a*v;W=V([-v[1],v[0]])*q**.5;N|={tuple(t)for t in[w+W,w-W]if all([L(t-T)>=s**2-1e-9 for T,s in I])}
N=map(V,N)
def T(a,b,c,p):H=[X(p-a,b-a),X(p-b,c-b),X(p-c,a-c)];return min(H)*max(H)>=0
def E(a,c,b):
 try:d=max((X(n-a,b-a)**2,id(n),n)for n in N if T(a,b,c,n)*X(n-b,c-b)*X(n-c,a-c))[2];A=E(a,c,d);B=E(d,c,b);return[A[0]+[d]+B[0],A[1]+[sign(X(c-a,b-c))]+B[1]]
 except:return[[]]*2
def P(I,c,r,A):
 H=[];M=[""]
 if L(c-e)>r*r:
    for C,R in I:
     if L(C-c)<=L(r+R)and all([L(h-C)>L(R+s)or any([T(c,C,h,p)for p in N])for h,s in H]):v=V(C);H+=[(v,R)];M=min(M,P(I-{(C,R)},v,R,A+[v]))
    return M
 A+=[e]*2;W=[.5]*len(A)
 try:
  while 1:
    i=[w%1*2or w==0for w in W[2:-2]].index(1);u,a,c,b,v=A[i:i+5];A[i+2:i+3],W[i+2:i+3]=t,_=E(a,c,b);t=[a]+t+[b]
    for p,q,j,k in(u,a,1,i+1),(v,b,-2,i+len(t)):x=X(q-p,c-q);y=X(q-p,t[j]-q);z=X(c-q,t[j]-q);d=sign(j*z);W[k]+=(x*y<=0)*(x*z<0 or y*z>0)*(x!=0 or d*W[k]<=0)*(y!=0 or d*W[k]>=0)*d
 except:return[sum(L(A[i+1]-A[i])**.5for i in range(len(A)-1)),id(A),A]
print V(P(I,e*0,0,[e*0]*2)[2][1:-1])

Входные данные задаются через переменную Iв виде набора кортежей, ((x, y), r)где (x, y)находится центр круга и rего радиус. Значения должны быть floats, а не ints. Результат распечатывается в STDOUT.

пример

# First test case
I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.)}

[[   0.            0.        ]
 [ 154.58723733  139.8329183 ]
 [ 169.69950891  152.76985495]
 [ 188.7391093   154.02738541]
 [ 325.90536774  109.74141936]
 [ 382.19108518  109.68789517]
 [ 400.00362897  120.91319495]
 [ 511.          511.        ]]