Algorithm
problem Link ; https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1861
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
nd 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 gure
on the right illustrates the cell numbering scheme.
The goal is, given the spiral tap coordinates of a cell, nd
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <iostream>
#include <fstream>
#include <sstream>
#include <cmath>
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
using namespace std;
int main(){
int a,b;
while(scanf("%d %d",&a,&b), a){
// compute size of square
int root = sqrt(b);
if(root % 2 == 0) root--;// round down even size
// compute starting position of 1,9,25...
// get middle square position and move top right
int row = (a/2+1) + root/2;
int col = row;
int remain = b - pow(root,2);
if(remain != 0) {
// compute direction coordinate is in
// north left south right
int direction = (remain-1)/(root+1);
remain = (remain-1) % (root+1);
if(direction == 0){
// north
row += 1;
col -= remain;
} else if(direction == 1){
// west
col -= root;
row -= remain;
} else if(direction == 2){
// south
row -= root;
col -= (root-1);
col += remain;
} else {
// east
col += 1;
row -= (root-1);
row += remain;
}
}
printf("Line = %d, column = %d.\n",row,col);
}
}
Input
3 3
3 9
5 9
5 10
0 0
Output
Line = 3, column = 1.
Line = 3, column = 3.
Line = 4, column = 4.
Line = 5, column = 4.
Demonstration
UVA Online Judge solution -10920-Spiral-Tap - UVA Online Judge solution in C,C++,java