UVa 1531 - Problem Bee
2024-09-01 11:01:55
题目:如图所看到的的蜂巢型的图中。蜜蜂想从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;
}
最新文章
- 安装php openssl扩展
- RBAC模型速记
- libpng使用
- SpringBoot应用部署[转]
- 《DSP using MATLAB》示例Example5.4
- MAT之prim算法
- R如何检验类别变量(nominal variable)与其他变量之间的相关性
- 关于delphi Assigned
- 解决JSP页面图片缓存问题
- opencv菜鸟学习之旅cvNorm
- Hibernate框架入门
- JavaScript new Date()在Safari上的坑
- oracle impdp将导出用户的所有对象导入至另一个用户下,生成的触发器语句问题处理
- scrapy系列(二)——startproject、genspider创建项目与模板使用
- Docker 配置阿里云镜像加速器
- Redis:五种数据类型的简单增删改查
- 函数名、闭包、装饰器 day11
- Spring 中的事务操作、注解、以及 XML 配置
- Web - TCP的三次握手
- Zabbix结合Grafana绘图