My solution is by simulating the cell numbering using array, then count the distance between 2 cells using phytagoras. It works well when i test it, but the judge give me WA

if someone have a better algorithm, or formula, please help me.
thanks
Moderator: Board moderators
Code: Select all
1 10000
10000 5
9999 10000
10000 10000
Code: Select all
58
58
1
0
Code: Select all
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
using namespace std;
int dx[] = {-1,-1, 0, 1,1,0};
int dy[] = { 1, 0,-1,-1,0,1};
#define C complex<int>
int grid[1000][1000];
C preq[10001];
int main(void) {
int a,b;
preq[1]=C(500,500);
C p(500,499);
int dir=0;
grid[500][500]=1;
for(int i=2; i<=10000; i++) {
grid[p.real()][p.imag()]=1;
preq[i]=p;
while(grid[p.real()+dx[dir]][p.imag()+dy[dir]]) dir=(dir+1)%6;
p+=C(dx[dir],dy[dir]);
dir=(dir+3)%6;
}
while((cin >> a >> b)&&(a+b)) {
if(a>10000 || b>10000 || a<1 || b<1) abort();
C p1 = preq[a];
C p2 = preq[b];
int ret=1000000;
int a = abs((p1-p2).real());
int b = abs((p1-p2).imag());
int c = abs((p1-p2).real()+(p1-p2).imag());
ret <?= a+b; ret <?= b+c; ret <?= c+a;
cout << ret << endl;
}
return 0;
}
Code: Select all
19 20
30 40
100 1
30 30
1 20
1 10
10 20
50 100
1 10000
1 1000
100 10000
5000 10000
8111 8222
5123 8000
1 1
2 2
3 3
3999 5699
0 0
Code: Select all
The distance between cells 19 and 20 is 1.
The distance between cells 30 and 40 is 7.
The distance between cells 100 and 1 is 6.
The distance between cells 30 and 30 is 0.
The distance between cells 1 and 20 is 3.
The distance between cells 1 and 10 is 2.
The distance between cells 10 and 20 is 3.
The distance between cells 50 and 100 is 7.
The distance between cells 1 and 10000 is 58.
The distance between cells 1 and 1000 is 18.
The distance between cells 100 and 10000 is 52.
The distance between cells 5000 and 10000 is 32.
The distance between cells 8111 and 8222 is 104.
The distance between cells 5123 and 8000 is 84.
The distance between cells 1 and 1 is 0.
The distance between cells 2 and 2 is 0.
The distance between cells 3 and 3 is 0.
The distance between cells 3999 and 5699 is 20.