場所

Question

からスパイラルインデックスを取得し、私はそれは受け入れ解決策ではないのですが、それは私のために最善の項目のインデックス

Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin

に基づくスパイラルグリッドの参照を取得するには、この質問へのアルベルト・サンティーニのソリューションを使用していますループを使用しないようにする必要があります。

これはうまくいっていますが、私が今したいのは、その逆を行うことです。既知のx座標とy座標に基づいて、場所のインデックスを返します。

これは、特定の場所の周囲のアイテムを返すための前提条件です。

Answer 1

パスカルコード：0-4-16-36-64左上半対角線（：

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; 

説明）には、2番目のレイヤ番号（4 * layer^2）が含まれます。外部ifステートメントは、レイヤーを定義し、左上のセミプレーンの対応する行または列内の位置の結果を検索し（pre-）、内部ifステートメントはミラー位置の結果を修正します。

Answer 2

あなたが望むものを導き出すための簡潔な数式があるのか​​どうかわかりませんが、クエリごとにO（1）時間内に何をしたいのかを計算するソリューションがあります。あなたが望むようなループはありません。

私のアプローチ：

任意の点（x、y）は、辺の長さの正方形にある点の数（2 * 1）=最大を見出すための式（I）（ | x |、| y |）これらは内点です。すなわち、現在のスパイラルを含まないすべてのスパイラルにあるポイントの数。

これは何もありませんが、（2 * A -1）*（2 * A -1）

例：点（2,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 
      | 
      | 

：次の図を考えてみましょう内側の点は、0,1,2,3,4,5,6,7,8とラベル付けされています。 - 辺の長さが3の正方形。

（ii）ここで、現在のスパイラル。 （現在のスパイラル開始）

（A）起点

（b）の点（A）

（C）点（ - スパイラル4 "コーナー" 点を有します-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)); 
     } 
    } 

}