首页 > 代码库 > UVa 1531 - Problem Bee
UVa 1531 - Problem Bee
题目:如图所示的蜂巢型的图中,蜜蜂想从A点飞到B点,如果A与B不在同一个正六边形中,
则它先飞到A的中心,每次飞到相邻格子的中心,最后飞到B的中心,再飞到B点;
如果在一个格子中,直接飞过去即可(观察第二组数据)。
分析:计算几何。设格子边长为a。
首先观察,所有格子的中心为(3xa/2,sqrt(3)ya/2),其中x、y为整数且奇偶性相同;
因此,根据给定点的坐标,可以求出A,B所在的格子的行列编号(处理奇偶性不同情况);
(由于,是取整计算,所以要要判断周围六个格子,是不是比自己更适合);
然后计算即可,其中:(观察可以发现只有数值和斜着走两种方式)
设x为横坐标编号差,y为纵坐标编号差;
如果,x >= y 则每次斜着走一定走到,所以中间路径长度为sqrt(3)*a*x;
否则,x < y 则多余的y要竖直方形行走,中间路径长度为sqrt(3)*a*((y-x)/ 2+r);
说明:注意编号奇偶同时的处理。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cmath> using namespace std; typedef struct pnode { double x,y; }point; point a,b; typedef struct snode { int r,l; }place; place p,q; point getpoint(int r, int l, double L) { point p; p.x = r*1.5*L; p.y = l*sqrt(3.0)/2.0*L; return p; } double dist(point p, point q) { return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y)); } int dxy[7][2] = {{0,0},{0,2},{-1,1},{1,1},{-1,-1},{1,-1},{0,-2}}; place getplace(point a, double L) { int r = (int)(2*a.x/L/3.0); int l = (int)(2*a.y/L/sqrt(3.0)); if (r%2 != l%2) { l = l+l%2; r = r+r%2; } int now = 0; for (int i = 1 ; i < 7 ; ++ i) if (dist(a, getpoint(r+dxy[i][0], l+dxy[i][1], L)) < dist(a, getpoint(r+dxy[now][0], l+dxy[now][1], L))) now = i; place s; s.r = r+dxy[now][0]; s.l = l+dxy[now][1]; return s; } int main() { double L,path,d1,d2; while (~scanf("%lf%lf%lf%lf%lf",&L,&a.x,&a.y,&b.x,&b.y) && L) { p = getplace(a, L); q = getplace(b, L); d1 = dist(a, getpoint(p.r, p.l, L)); d2 = dist(b, getpoint(q.r, q.l, L)); int r = abs(p.r-q.r),l = abs(p.l-q.l); if (r >= l) path = r*L*sqrt(3.0); else path = ((l-r)/2+r)*L*sqrt(3.0); if (r+l) printf("%.3lf\n",path+d1+d2); else printf("%.3lf\n",path+dist(a,b)); } return 0; }
UVa 1531 - Problem Bee
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。