uva 1531 & poj 1518 Problem Bee(几何计算+贪心）

题目链接：UVa1531&poj 1518Problem Bee

题目大意：在个坐标系上布满了正六边行，其中一个以原点为中心，给出六边形得边长以及A、B点的坐标，现在有一只蜜蜂要从A点移动到B点，为了防止自己迷路，它会先移动到A点所在的六边形的中心，然后从这个中心移动到相邻六边形的中心，直到移动到B点所在六边形的中心后，直接移动到B点，问说蜜蜂走过的最短距离为多少。

解题思路：题目中没有说如果A、B在同一个六边形中可以不用移动到中心，到时样例很明显就是这样。而且这道题在poj上过掉了，但是在uva上老是WA，找了一大堆pojAC的代码都没办法过，求大神指点，是不是uva数据坏掉了？

我的做法，将x坐标按照单位长度为3r/2，y坐标单位长度按照sqrt(3)r/2，确立模拟的坐标系，然后cx+cy为偶数的点即为某一个六边形的中心。首先找到A、B所在的六边形中心，如果相同的话直接输出两点的距离。保险起见我还将x，y坐标取整后周围的几个点一起考虑了一遍，确定最近的中心。然后从A'到B‘就用贪心的思想，取横坐标差和纵坐标差的最大值。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>

using namespace std;
const double sq3 = sqrt(3.0);
const double INF = 0x3f3f3f3f;
const int d[7][2] = { {0, 0}, {0, -2}, {0, 2}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
struct point {
	double x, y;
};
double tx, ty;

double dis(double x, double y) {
	return sqrt(x*x+y*y);
}

point find(double xi, double yi) {
	int cx = (int)(xi/tx);
	int cy = (int)(yi/ty);
	if (cx&1) {
		if (cy%2 == 0) cy++;
	} else {
		if (cy%2) cx++;
	}
	
	point A;
	double tmp = INF;

	for (int i = 0; i < 7; i++) {
		double a = dis((cx+d[i][0])*tx-xi, (cy+d[i][1])*ty-yi);
		if (a < tmp) {
			A.x = (cx+d[i][0])*tx;
			A.y = (cy+d[i][1])*ty;
			tmp = a;
		}
	}
	return A;
}

double solve(point A, point B) {
	int cx = (int)(fabs(A.x-B.x)/tx+0.5);
	int cy = (int)(fabs(A.y-B.y)/ty+0.5);
	return max(cx, cy) * sq3;
}

int main () {
	double r, x1, y1, x2, y2;	
	while (scanf("%lf%lf%lf%lf%lf", &r, &x1, &y1, &x2, &y2) == 5 && (r||x1||y1||x2||y2)) {
		tx = 3*r/2; ty = sq3*r/2;
		point A = find(x1, y1);
		point B = find(x2, y2);

		if (fabs(A.x-B.x) < 1e-9 && fabs(A.y-B.y) < 1e-9) {
			printf("%.3lf\n", dis(x1-x2, y1-y2));
		} else {
			double len = dis(A.x-x1, A.y-y1) + dis(B.x-x2, B.y-y2);
			len = len + solve(A, B)*r;
			printf("%.3lf\n", len);
		}
	}
	return 0;
}

经过大神指教，已AC，主要有两个问题，一是先要将坐标转换成正值再取确定位置，二是如果纵坐标大于横坐标式，纵坐标的单位两个等于一步。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>

using namespace std;
const double sq3 = sqrt(3.0);
const double INF = 0x3f3f3f3f;
const int d[7][2] = { {0, 0}, {0, -2}, {0, 2}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
struct point {
	double x, y;
};
double tx, ty;

inline double dis(double x, double y) {
	return sqrt(x*x+y*y);
}

point findPos (double xi, double yi) {
	int cx = (int)(xi/tx);
	int cy = (int)(yi/ty);
	if (cx&1) {
		if (cy%2 == 0) cy++;
	} else {
		if (cy%2) cx++;
	}
	
	point A;
	double tmp = INF;

	for (int i = 0; i < 7; i++) {
		double a = dis((cx+d[i][0])*tx-xi, (cy+d[i][1])*ty-yi);
		if (a < tmp) {
			A.x = (cx+d[i][0])*tx;
			A.y = (cy+d[i][1])*ty;
			tmp = a;
		}
	}
	return A;
}

point find (double xi, double yi) {
	point ans;

	if (xi > 0 && yi > 0) {
		ans = findPos(xi, yi);
	} else if (xi < 0 && yi < 0) {
		ans = findPos(-xi, -yi);
		ans.x = -ans.x;
		ans.y = -ans.y;
	} else if (xi < 0 && yi > 0) {
		ans = findPos(-xi, yi);
		ans.x = -ans.x;
	} else {
		ans = findPos(xi, -yi);
		ans.y = -ans.y;
	}
	return ans;
}

double solve(point A, point B) {
	int cx = (int)(fabs(A.x-B.x)/tx+0.5);
	int cy = (int)(fabs(A.y-B.y)/ty+0.5);
	if (cx >= cy)
		return cx * sq3;
	else
		return (cx + (cy - cx) / 2.0) * sq3;
	/*
	return max(cx, cy) * sq3;
		*/
}

int main () {
	double r, x1, y1, x2, y2;	
	while (scanf("%lf%lf%lf%lf%lf", &r, &x1, &y1, &x2, &y2) == 5 && (r||x1||y1||x2||y2)) {
		tx = 3*r/2; ty = sq3*r/2;
		point A = find(x1, y1);
		point B = find(x2, y2);

		if (fabs(A.x-B.x) < 1e-9 && fabs(A.y-B.y) < 1e-9) {
			printf("%.3lf\n", dis(x1-x2, y1-y2));
		} else {
			double len = dis(A.x-x1, A.y-y1) + dis(B.x-x2, B.y-y2);
			len = len + solve(A, B)*r;
			printf("%.3lf\n", len);
		}
	}
	return 0;
}