问题描述
蜂巢由六边形拼接而成，定义蜂巢中的方向：0表示正西方向，1表示西偏北60°，2表示东偏北60°，3表示正东，4表示东偏南60°，5表示西偏南60°。
对于给定的一点O，以O为原点定义坐标系，如果一个点A由O点先向d方向走p步再向(d + 2) mod 6方向（d的顺时针120°向）走q步到达，则这个点的坐标定义为(d, p, q)。在蜂窝中，一个点的坐标可能有多种。 图给出了点B(0, 5, 3)和点C(2, 3, 2)的示意。
给定点(d1, p1, q1)和点(d2, p2, q2)，请问他们之间最少走多少步可以到达？
输入格式
输入一行包含 6 个整数 d1,p1,q1,d2,p2,q2 表示两个点的坐标，相邻两个整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示两点之间最少走多少步可以到达。
数据范围
对于 25% 的评测用例，p1,p2≤103；
对于 50% 的评测用例，p1,p2≤105；
对于 75% 的评测用例，p1,p2≤107；
对于所有评测用例，0≤d1,d2≤5，0≤q1<p1≤109，0≤q2<p2≤109。
输入样例：
0 5 3 2 3 2
输出样例：
7
思路
这道题从图上来看其实并不难，假设我要从 B 到 C 找到最短路径，实际上就只能从右下走，但是难就难在这题没有给定坐标系，坐标系需要我们自己分析构建。
我们以 O 点为原点，以每个蜂巢的中心点作为每一处坐标，构建坐标系：
观察上图可知，如果直接用曼哈顿距离公式来计算两点之间的距离是不正确的，但可以发现如下规律（假设两点之间的横坐标之差的绝对值为 d x = ∣ x 1 − x 2 ∣ dx=|x1-x2|dx=∣x1−x2∣，纵坐标之差的绝对值为 d y = ∣ y 1 − y 2 ∣ dy=|y1-y2|dy=∣y1−y2∣）：
如果 dx 大于 dy，则两点之间的距离为 ( d x + d y ) / 2 (dx+dy)/2(dx+dy)/2
如果 dx 小于 dy，则两点之间的距离为 d y dydy
如果 dx 等于 dy，上面的两种公式都能得到正确答案
举个例子，假设从 (-1,1) 到 (1,-1)，其 dx 和 dy 分别为 2 和 3。故 dy 大于 dx ，则最少要走 3 步。
再举个例子，假设从 (-1,1) 到 (2,0)，其 dx 和 dy 分别为 3 和 1。故 dx 大于 dy，则最少要走 (1+3)/2=2 步。
代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; LL d1, p1, q1, d2, p2, q2; LL dx[] = { -2,-1,1,2,1,-1 }, dy[] = { 0,1,1,0,-1,-1 }; void walk(LL d, LL s, LL& x, LL& y) { x += dx[d] * s; y += dy[d] * s; } int main() { cin >> d1 >> p1 >> q1 >> d2 >> p2 >> q2; //计算第一个坐标 LL x1 = 0, y1 = 0; walk(d1, p1, x1, y1); walk((d1 + 2) % 6, q1, x1, y1); //计算第二个坐标 LL x2 = 0, y2 = 0; walk(d2, p2, x2, y2); walk((d2 + 2) % 6, q2, x2, y2); //计算dx和dy LL dx = abs(x1 - x2), dy = abs(y1 - y2); //根据计算结果输出对应答案 if (dx >= dy) cout << (dx + dy) / 2 << endl; else cout << dy << endl; return 0; }
