Created
February 26, 2014 01:06
-
-
Save rayjcwu/9221420 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.Scanner; | |
| public class HoneyComb { | |
| public static void main(String []argv) throws Exception { | |
| HoneyComb hc = new HoneyComb(); | |
| hc.enter(); | |
| } | |
| public void enter() { | |
| Scanner scanner = new Scanner(System.in); | |
| final long A = scanner.nextLong(); | |
| final long B = scanner.nextLong(); | |
| Coord a = toCoord(A); | |
| Coord b = toCoord(B); | |
| System.out.println(dist(a, b)); | |
| } | |
| // number of accumulate elements till x-th wrap | |
| private long accu(long x) { | |
| return 1 + 3 * (x + 1) * x; | |
| } | |
| private long initX(long N) { | |
| long x = 0; | |
| while (accu(x + 1) < N) { | |
| x++; | |
| } | |
| return x; | |
| } | |
| // (x, y) movement in six different area | |
| final int []xMove = {-1, -1, 0, 1, 1, 0}; | |
| final int []yMove = {-1, 0, 1, 1, 0, -1}; | |
| private Coord toCoord(long N) { | |
| if (N == 1) { | |
| return new Coord(0, 0); | |
| } else { | |
| long x = initX(N); | |
| long y = 0; | |
| long left = N - accu(x); | |
| if (left == 0) { | |
| return new Coord(x, y); | |
| } | |
| // move around hex | |
| x++; | |
| final long step = x; | |
| int area = 0; | |
| while (left > 0) { | |
| if (left <= step) { | |
| x += left * xMove[area]; | |
| y += left * yMove[area]; | |
| break; | |
| } else { | |
| left -= step; | |
| x += step * xMove[area]; | |
| y += step * yMove[area]; | |
| area++; | |
| } | |
| } | |
| return new Coord(x, y); | |
| } | |
| } | |
| private long dist(Coord a, Coord b) { | |
| // move along (1, 0), (0, 1), (1, 1) axis | |
| // dist 1 is moving along (1, 0) and (0, 1) | |
| final long d1 = Math.abs(a.x - b.x) + Math.abs(a.y - b.y); | |
| // dist 2 is moving along (1, 1) and (1, 0) | |
| // first move a.y to b.y along (1, 1), calculate new x | |
| long dir = b.y - a.y; | |
| long tx = a.x + dir; | |
| // then move a.x to b.x along (1, 0) | |
| final long d2 = Math.abs(dir) + Math.abs(tx - b.x); | |
| // dist 3 is moving along (1, 1) and (0, 1) | |
| // first move a.x to b.x along (1, 1), calculate new y | |
| dir = b.x - a.x; | |
| long ty = a.y + dir; | |
| // then move a.y to b.y along (0, 1) | |
| final long d3 = Math.abs(dir) + Math.abs(ty - b.y); | |
| return Math.min(Math.min(d1, d2), d3); | |
| } | |
| } | |
| class Coord { | |
| long x; | |
| long y; | |
| public Coord(long x, long y) { | |
| this.x = x; | |
| this.y = y; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment