Получить спиральный указатель с места

Question

Я использую решение Альберто Сантини для этого вопроса, чтобы получить ссылку на спиральную сетку на основе индекса элементов

Алгоритм итерации по внешней спирали на дискретной двумерной сетке от источника

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

Это работает хорошо, но сейчас я хочу сделать обратное.Основанный на известных координатах x и y, возвращает индекс местоположения.

Это предвестник возврата предметов, окружающих данное местоположение.

Answer 1

Код Паскаля:

if y * y >= x * x then begin
  p := 4 * y * y - y - x;
  if y < x then
    p := p - 2 * (y - x)
end
else begin
  p := 4 * x * x - y - x;
  if y < x then
    p := p + 2 *(y - x)
end;

Описание: Левая верхняя полудиагональ (0-4-16-36-64) содержит номер слоя в квадрате (4 * layer ^ 2). Внешний оператор if определяет слой и находит (предварительно) результат для позиции в соответствующей строке или столбце левой-верхней полуплоскости, а внутренний оператор if корректирует результат для зеркальной позиции.

Answer 2

Я не знаю, есть ли краткое математическое уравнение для получения того, что вы хотите, но у меня есть решение, которое вычисляет то, что вы хотите, за O (1) раз за запрос.Нет петель, как вы хотели.

Мой подход:

(i) Для любой заданной точки (x, y) найдите количество точек, лежащих в квадрате длины стороны (2 *a-1), где a = Max (| x |, | y |).Это внутренние точки.т.е. число точек, лежащих во всех спиралях, НЕ включая текущую спираль.

Это не что иное, как (2 * a -1) * (2 * a -1)

Например: рассмотримследующая диаграмма:

y
          |
          |
   16 15 14 13 12
   17  4  3  2 11
-- 18  5  0  1 10 --- x
   19  6  7  8  9
   20 21 22 23 24
          |
          |

Для точки (2,1), a = 2. Внутренние точки здесь обозначены как 0, 1, 2, 3, 4, 5, 6, 7, 8- Квадрат с длиной ребра 3

(ii) Теперь вычислите точки, лежащие на текущей спирали.Спираль имеет 4 «угловые» точки -

(a) Начальная точка (где начинается текущая спираль)

(b) Точка (a, a)

(c) Точка (-a, a)

(d) Точка (-a, -a)

Итак, я вычисляю количество элементов, лежащих между каждой такой парой [т.е.между (a) и (b), (b) и (c), (c) и (d)], так что все они попадают до требуемой точки входа в спиральной последовательности.Это можно сделать простым вычитанием координат точек.

Это значение плюс количество внутренних точек даст вам требуемый ответ.

Я не уверен, объяснил ли я этоочень четкоДайте мне знать, если вам потребуются какие-либо разъяснения или дальнейшие объяснения.

Прилагается код JAVA, который я написал для проверки моей логики.Извините, но это не очень элегантно, но работает: P

import java.io.IOException;
import java.util.Scanner;

class Pnt
{
    int x, y;

    public Pnt( int _x, int _y )
    {
        x = _x;
        y = _y;
    }
}

public class Spiral
{

    static int interior( Pnt p ) // returns points within interior square of side length MAX( x, y ) - 1
    {
        int a = Math.max( Math.abs( p.x ), Math.abs( p.y ));
        return ( 2*a - 1 )*( 2*a - 1 );
    }


    static Pnt startPnt( Pnt p ) // first point in that spiral
    {
        int a = Math.max( Math.abs( p.x ), Math.abs( p.y ));

        // last pnt in prev spiral = [ a-1, -( a-1 ) ]

        // next pnt  = [ a, -( a-1 ) ]

        return new Pnt( a, -( a-1 ));
    }

    static int offSetRow1( Pnt pStart, Pnt p )
    {

        return ( p.y - pStart.y ) + 1;
    }



    static int solve( Pnt curr )
    {
        // check location of curr
        // It may lie on 1st row, 2nd row, 3rd or 4th row

        int a = Math.max( Math.abs( curr.x ), Math.abs( curr.y ));
        int off=0;
        int interiorCnt = interior( curr );
        Pnt start = startPnt( curr );

        if( ( curr.x == a ) && ( curr.y >= start.y ) ) // row 1
        {
            off = offSetRow1( start, curr );
            return off+interiorCnt;
        }

         if( curr.y == a ) // row 2
        {
            Pnt start2 = new Pnt( a, a );
            int off1 = offSetRow1( start, start2 );

            // now add diff in x-coordinates

            int off2 = start2.x - curr.x;
            off = off1 + off2;
            return off+interiorCnt;

        }

        if( curr.x == -a ) // row 3
        {
            Pnt start2 = new Pnt( a, a );
            int off1 = offSetRow1( start, start2 );

            // now add diff in x-coordinates

            Pnt start3 = new Pnt( -a, a );
            int off2 = start2.x - start3.x;

            // now add diff in y co-ordinates


            int off3 = start3.y - curr.y;

            off = off1 + off2 + off3;
            return off+interiorCnt;

        }

        else // row 4
        {
             Pnt start2 = new Pnt( a, a );
            int off1 = offSetRow1( start, start2 );

            // now add diff in x-coordinates

            Pnt start3 = new Pnt( -a, a );
            int off2 = start2.x - start3.x;

            // now add diff in y co-ordinates


            int off3 = start3.y - curr.y;

            Pnt start4 = new Pnt( -a, -a );

            // add diff in x co-ordinates

            int off4 = curr.x - start4.x;
            off = off1 + off2 + off3 + off4;
            return interiorCnt + off;
        }


    }

    public static void main( String[] args ) throws IOException
    {
        Scanner s = new Scanner( System.in );

        while( true )
        {
            int x = s.nextInt();
            int y = s.nextInt();

            Pnt curr = new Pnt( x, y );
            System.out.println( solve( curr ));
        }
    }

}