Problem A - Spiral Tap

Time Limit: 1 second

The game of Spiral Tap is played on a square grid. Pieces are placed on a grid and the moves are realized according to the position of the pieces on the grid. However, the coordinate system in the game of Spiral Tap are a bit different that those find in traditional board games, such as chess.

The cell numbering scheme follow a spiral, starting from the center of the grid in an anti-clockwise fashion. The following figure illustrates the cell numbering scheme.

The goal is, given the spiral tap coordinates of a cell, find its cartesian coordinates (line 1 is at the bottom, and column 1 is the leftmost).

Input

The input is a series of lines. Each line is composed of two numbers: SZ and P. SZ is the size of the border of the grid and is an odd number no larger than 100000. P is the spiral position of a cell in this grid. The line such that SZ = P = 0 marks the end of the input (and is not part of the data set).

Output

For each line in the data set of the input, your program must echo a line "Line = X, column = Y.", where X and Y are the cartesian coordinates of the corresponding cell.

Sample Input

3 1
3 3
3 9
5 9
5 10
0 0

Sample Output

Line = 2, column = 2.
Line = 3, column = 1.
Line = 3, column = 3.
Line = 4, column = 4.
Line = 5, column = 4.

---

Problem setter: David Deharbe, Copyright 2005 UFRN. All rights reserved.

算一下在第幾層, 然後定為點在右上角, 再依序扣回來直到算到答案為止。


#include <stdio.h>
#include <math.h>
int main() {
    int n, m;
    while(scanf("%d %d", &n, &m) == 2 && n) {
        int x = n/2+1, y = n/2+1, z, w;
        int sq = (int)sqrt(m);
        if(sq%2 == 0)   sq--;
        for(z = sq; z*z < m; z += 2);
        w = z/2;
        x += w, y += w;
        int v = z*z;
        if(v - z < m) {
            y -= v - m;

            goto end;
        } else
            y -= z-1, v -= z, x--;

        if(v - z + 1 < m) {
            x -= v - m;
            goto end;
        } else
            x -= z-2, v -= z-1, y++;

        if(v - z + 1 < m) {
            y += v - m;
            goto end;
        } else
            y += z-2, v -= z-1, x++;
        if(v - z + 1 < m) {
            x += v - m;
            goto end;
        } else
            x += z-2, v -= z-1;
        end:
        printf("Line = %d, column = %d.\n", y, x);
    }
    return 0;
}