[UVA] 10964 - Strange Planet
Problem A
Strange Planet
As you know, there are many strange planets in the universe. Dara and Sara are living in one of these strange planets with an unusual coordinate system. This Planet is like a grid having unit-sized cells with the houses considered as points placed in the center of cells. The cells are assigned a unique number as shown in figure 1.
. |
|
|
|
|
|
|
|
. |
|
. |
|
|
15 |
|
|
. |
|
|
|
. |
14 |
6 |
16 |
. |
|
|
|
|
13 |
5 |
1 |
7 |
17 |
|
|
|
24 |
12 |
4 |
0 |
2 |
8 |
18 |
|
|
|
23 |
11 |
3 |
9 |
19 |
|
|
|
|
. |
22 |
10 |
20 |
. |
|
|
|
. |
|
|
21 |
|
|
. |
|
. |
|
|
|
|
|
|
|
. |
Figure 1. The Strange Planet
Recently, Dara and Sara have become familiar with the well-known Cartesian coordinate system based on X and Y axes, and would like to know the Euclidian distance between their houses. Unfortunately, they don’t know how to calculate this distance. So, they need your help to calculate it. You may assume that the cell with number 0 is located at the origin (with coordinate (0, 0)) of the Cartesian coordinate system.
The Input
Input file consists of many test-cases. Each test-case consists of two integers indicating the cell numbers that contain their houses. The input will be terminated with a line containing two -1s.
The Output
For each test-case, print the Euclidian distance between the houses of Dara and Sara rounded to two digits after the fraction point.
Sample Input
2 7
29 32
-1 -1
Sample Output
1.00
4.24
Amirkabir University of Technology - Local Contest - Round #2
這種計算問題,一律先考量第幾層之後再進行回扣。
#include <stdio.h>
#include <math.h>
void getXY(int n, int &x, int &y) {
int level = 0, sum = 1;
while(sum <= n) {
level++;
sum += level*4;
}
sum--;
x = -level, y = 0;
if(n >= sum-level) {
x += sum-n, y -= sum-n;
return;
} else
sum -= level, x = 0, y = -level;
if(n >= sum-level) {
x += sum-n, y += sum-n;
return;
} else
sum -= level, x = level, y = 0;
if(n >= sum-level) {
x -= sum-n, y += sum-n;
return;
} else
sum -= level, x = 0, y = level;
x -= sum-n, y -= sum-n;
return;
}
int main() {
int a, b;
while(scanf("%d %d", &a, &b) == 2 && a >= 0) {
int ax, ay, bx, by;
getXY(a, ax, ay);
getXY(b, bx, by);
printf("%.2lf\n", hypot(ax-bx, ay-by));
}
return 0;
}