在上周的CCPC秦皇岛中,我们在热身赛就“出师不利”,被一道计算几何斩下马。所以我开始祈祷天堂没有计算几何(误),所以我开始主攻计算几何这一部分。在这篇BLOG中,我们就来一同解决长方体两点的最短表面距离这一看似简单实则十分繁杂的问题吧!由于这个问题在网络上的讨论甚少,仅有的一份CSDN上的模板也是错误的,所以本片BLOG也是没有任何参考的完全原创BLOG。如果本篇BLOG出现任何错误,欢迎指正!
思考一下
问题描述
让我们先思考一个问题,对于一个给定的长方体(如下图所示),其沿着x轴的边长是a,沿着y轴的边长是b,沿着z轴的边长是c:
现在我们的小蒟蒻站在这个长方体表面上的任意一点A上,他的家在长方体表面上的另一点B点上。为了方便接下来的讨论,我们约定A点在长方体的上表面上。现在小蒟蒻想要沿着长方体的外表面从A点走到B点(如下图橙色路径为一条可行路径),给出A点和B点的坐标,请问他需要走过的最短距离是多少呢?
解题思路
这题应该算得上是非常典型的三维计算几何题目了。为了方便计算,我们可以把问题分为三种大的情况进行分类讨论:AB两点处在同一面上,AB处在相邻面上和AB处在对立面上:
AB处在同一面上
我们先来看看最简单的一种情况,AB处在同一面上。我们知道空间上AB两点的最短距离就是这两点在空间上的连线。而此时A和B恰好处在同一平面上,所以在这一平面上A到B的线段就是这两点在空间上的连线也就是最短距离:
故我们直接连接AB,线段AB就是沿着AB在空间上的最短距离,肯定也是长方体的外表面从A点走到B点的最短距离。
这时如果给定A(xa, ya, za),B(xb, yb, zb),由于此时A一定位于长方体的上平面故za = c
(题目约定),故要想B和A处于同一平面,也只能在zb = c
的情况下,所以则此时A到B的距离就可以通过下面这个代码进行计算:
//A和B同在上表面(同一个面)的情况
if (zb == c) {
dx = fabs(xa - xb);
dy = fabs(ya - yb);
ans = calc(dx, dy);
}
其中我们的calc是通过dx和dy计算距离的函数:
double calc(double x, double y) {
double ans = sqrt(x * x + y * y);
return(ans);
}//勾股定理计算
这种情况就顺利解决啦。
AB处在相邻面上
从这种情况开始,问题就变得复杂起来了。由于在立体图形上计算表面距离非常麻烦,所以我们考虑将这个长方体展开。由于B处在不同的面上,需要展开的面不同计算公式也有区别,确定一个统一的计算公式非常困难。所以为了降低思维难度,我们这里运用分类讨论的方法进行计算。
B在左侧面
如果这个时候B在左侧面,那最短距离怎么求呢?首先我们很容易想到,最短路径可能是只经过上顶面和左侧面这两个面。这时我们只要可接把左侧面展开上去,和A所在的上顶面形成一个平面,然后利用AB两点之间的距离进行求解就可以啦:
这时我们很容易看出此时两点之间横向距离dx = xa + (c - zb)
,纵向距离dy = fabs(ya - yb)
。这时只要利用dis = sqrt(dx * dx + dy * dy)
就能算出AB两点的距离了。
那到这里是不是就结束了呢?当然没有。相邻两个面上两个点的最短表面距离线路还有可能经过三个面!
这时又分为两种情况,第一种是展开上顶面,前侧面和左侧面这三个面:
这时我们可以看到,dx = xa + yb
,纵向距离dy = ya + (c - zb)
,我们继续用dis = sqrt(dx * dx + dy * dy)
更新答案。
第二种情况是展开上顶面,后侧面和左侧面这三个面:
这时我们可以看到,dx = xa + (b - yb)
,纵向距离dy = (b - ya) + (c - zb)
,我们继续用dis = sqrt(dx * dx + dy * dy)
更新答案。
所以这一小部分的代码为:
if (xb == 0) {
//展开两个面
dx = xa + (c - zb);
dy = fabs(ya - yb);
ans = calc(dx, dy);
//展开三个面
//情况1
dx = xa + yb;
dy = ya + (c - zb);
ans = min(ans, calc(dx, dy));
//情况2
dx = xa + (b - yb);
dy = (b - ya) + (c - zb);
ans = min(ans, calc(dx, dy));
}
到这里我们就完成了对B在左侧面的讨论。那可能会有细心的同学问了,为什么我们只考虑了经过两个面和三个面这两种情况,那四个面五个面六个面的情况呢?其实你自己画一下图就知道了随着经过的无关面的增加,两点之间的横向距离和纵向距离也是会慢慢增加的,所以自己画画图就可以发现对于相邻面的点,只考虑经过两个面和三个面就已经足够啦。
B在右侧面
当B在右侧面的时候,情况和在左侧面的情况其实是非常类似的。
首先我们先考虑路径只经过上顶面和右侧面的情况,这样展开来看就是下面这样:
这时我们很容易看出此时两点之间横向距离dx = (a - xa) + (c - zb)
,纵向距离dy = fabs(ya - yb)
。这时一样地我们只要利用dis = sqrt(dx * dx + dy * dy)
就能算出AB两点的距离了。
接下来我们来考虑经过三个面的两种情况。第一种是经过上顶面,前侧面和右侧面的情况:
这时横向距离dx = (a - xa) + yb
,纵向距离dy = ya + (c - zb)
,我们用dis = sqrt(dx * dx + dy * dy)
更新答案。
第二种则是经过上顶面,后侧面和右侧面的情况:
这时横向距离dx = (a - xa) + (b - yb)
,纵向距离dy = (b - ya) + (c - zb)
,我们继续用dis = sqrt(dx * dx + dy * dy)
更新答案。
故这一部分的代码为:
if (xb == a) {
//展开两个面
dx = (a - xa) + (c - zb);
dy = fabs(ya - yb);
ans = calc(dx, dy);
//展开三个面
//情况1
dx = (a - xa) + yb;
dy = ya + (c - zb);
ans = min(ans, calc(dx, dy));
//情况2
dx = (a - xa) + (b - yb);
dy = (b - ya) + (c - zb);
ans = min(ans, calc(dx, dy));
}
B在前侧面
当B在前侧面的时候,情况和之前比较类似但是由于这次不是左右面的展开是前后面的展开所以对应的坐标变化会有一些区别。
首先我们先考虑路径只经过上顶面和前侧面的情况,这样展开来看就是下面这样:
这时我们很容易看出此时两点之间横向距离dx = fabs(xa - xb)
,纵向距离dy = ya + (c - zb)
。这时一样地我们只要利用dis = sqrt(dx * dx + dy * dy)
就能算出这时AB两点的距离了。
接下来我们来考虑经过三个面的两种情况。第一种是经过上顶面,左侧面和前侧面的情况:
这时横向距离dx = xa + (c - zb)
,纵向距离dy = ya + xb
,我们用dis = sqrt(dx * dx + dy * dy)
更新答案。
第二种则是经过上顶面,右侧面和前侧面的情况:
这时横向距离dx = (a - xa) + (c - zb)
,纵向距离dy = ya + (a - xb)
,我们继续用dis = sqrt(dx * dx + dy * dy)
更新答案。
故这一部分的代码为:
if (yb == 0) {
//展开两个面
dx = fabs(xa - xb);
dy = ya + (c - zb);
ans = calc(dx, dy);
//展开三个面
//情况1
dx = xa + (c - zb);
dy = ya + xb;
ans = min(ans, calc(dx, dy));
//情况2
dx = (a - xa) + (c - zb);
dy = ya + (a - xb);
ans = min(ans, calc(dx, dy));
}
B在后侧面
当B在后侧面的时候,情况和在后侧面的考虑也基本是一样的。
首先我们先考虑路径只经过上顶面和后侧面的情况,这样展开来看就是下面这样:
这时我们很容易看出此时两点之间横向距离dx = fabs(xa - xb)
,纵向距离dy = (b - ya) + (c - zb)
。这时一样地我们只要利用dis = sqrt(dx * dx + dy * dy)
就能算出这时AB两点的距离了。
接下来我们来考虑经过三个面的两种情况。第一种是经过上顶面,左侧面和后侧面的情况:
这时横向距离dx = xa + (c - zb)
,纵向距离dy = (b - ya) + xb
,我们用dis = sqrt(dx * dx + dy * dy)
更新答案。
第二种则是经过上顶面,右侧面和后侧面的情况:
这时横向距离dx = (a - xa) + (c - zb)
,纵向距离dy = (b - ya) + (a - xb)
,我们继续用dis = sqrt(dx * dx + dy * dy)
更新答案。
故这一部分的代码为:
if (yb == b) {
//展开两个面
dx = fabs(xa - xb);
dy = (b - ya) + (c - zb);
ans = calc(dx, dy);
//展开三个面
//情况1
dx = xa + (c - zb);
dy = (b - ya) + xb;
ans = min(ans, calc(dx, dy));
//情况2
dx = (a - xa) + (c - zb);
dy = (b - ya) + (a - xb);
ans = min(ans, calc(dx, dy));
}
AB处在对立面上
这应该是最复杂的一种情况了。一共是有两大类十二种情况需要讨论。
经过三个面
我们还是由浅入深,先来看看最简单的情况,只经过三个面的情况吧。由于处在对立面,又需要经过刚好三个面到达,所以路径肯定是依次经过上顶面——某一个侧面——下底面。所以我们需要做的就是去讨论经过了哪个侧面,这里就分为四种情况。
首先是经过左侧面的情况,我们将左侧面和下底面展开:
这时我们很容易看出此时两点之间横向距离dx = xa + c + xb
,纵向距离dy = fabs(ya - yb)
。这时一样地我们只要利用dis = sqrt(dx * dx + dy * dy)
就能算出这时AB两点的距离了。
然后是经过右侧面的情况,我们将右侧面和下底面展开:
这时横向距离dx = (a - xa) + c + (a - xb)
,纵向距离dy = fabs(ya - yb)
,我们继续用dis = sqrt(dx * dx + dy * dy)
更新答案。
接着是经过前侧面的情况,我们将前侧面和下底面展开:
这时横向距离dx = fabs(xa - xb)
,纵向距离dy = ya + c + yb
,我们接着用dis = sqrt(dx * dx + dy * dy)
更新答案。
最后是经过后侧面的情况,我们将后侧面和下底面展开:
这时横向距离dx = fabs(xa - xb)
,纵向距离dy = (b - ya) + c + (b - yb)
,我们最后用dis = sqrt(dx * dx + dy * dy)
更新答案。
所以这一部分总的代码为:
//经过三个面
//经过左侧面
dx = xa + c + xb;
dy = fabs(ya - yb);
ans = calc(dx, dy);
//经过右侧面
dx = (a - xa) + c + (a - xb);
dy = fabs(ya - yb);
ans = min(ans, calc(dx, dy));
//经过前侧面
dx = fabs(xa - xb);
dy = ya + c + yb;
ans = min(ans, calc(dx, dy));
//经过后侧面
dx = fabs(xa - xb);
dy = (b - ya) + c +(b - yb);
ans = min(ans, calc(dx, dy));
经过四个面
先经过左侧面
首先是首先经过左侧面的情况。在这种情况下又分为两种情况,一种是上顶面-左侧面-前侧面-下底面;一种是上顶面-左侧面-后侧面-下底面。我们也一种一种来看。
首先是依次经过上顶面-左侧面-前侧面-下底面,我们将其展开:
这时横向距离dx = xa + c + yb
,纵向距离dy = ya + xb
,我们用dis = sqrt(dx * dx + dy * dy)
更新答案。
接着是依次经过上顶面-左侧面-后侧面-下底面的情况,我们也将其展开:
这时横向距离dx = xa + c + (b - yb)
,纵向距离dy = (b - ya) + xb
,我们用dis = sqrt(dx * dx + dy * dy)
更新答案。
所以这一部分的代码为:
//先经过左侧面
//情况1
dx = xa + c + yb;
dy = ya + xb;
ans = min(ans, calc(dx, dy));
//情况2
dx = xa + c + (b - yb);
dy = (b - ya) + xb;
ans = min(ans, calc(dx, dy));
先经过右侧面
然后是首先经过右侧面的情况。在这种情况下又分为两种情况,一种是上顶面-右侧面-前侧面-下底面;一种是上顶面-右侧面-后侧面-下底面。
首先是依次经过上顶面-右侧面-前侧面-下底面,我们将其展开:
这时横向距离dx = (a - xa) + c + yb
,纵向距离dy = ya + (a - xb)
,我们用dis = sqrt(dx * dx + dy * dy)
更新答案。
接着是依次经过上顶面-右侧面-后侧面-下底面的情况,我们也将其展开:
这时横向距离dx = (a - xa) + c + (b - yb)
,纵向距离dy = (b - ya) + (a - xb)
,我们用dis = sqrt(dx * dx + dy * dy)
更新答案。
所以这一部分的代码为:
//先经过右侧面
//情况1
dx = (a - xa) + c + yb;
dy = ya + (a - xb);
ans = min(ans, calc(dx, dy));
//情况2
dx = (a - xa) + c + (b - yb);
dy = (b - ya) + (a - xb);
ans = min(ans, calc(dx, dy));
先经过前侧面
接着是首先经过前侧面的情况。在这种情况下又分为两种情况,一种是上顶面-前侧面-左侧面-下底面;一种是上顶面-前侧面-右侧面-下底面。
首先是依次经过上顶面-前侧面-左侧面-下底面,我们将其展开:
这时横向距离dx = xa + yb
,纵向距离dy = ya + c + xb
,我们用dis = sqrt(dx * dx + dy * dy)
更新答案。
接着是依次经过上顶面-右侧面-后侧面-下底面的情况,我们也将其展开:
这时横向距离dx = (a - xa) + yb
,纵向距离dy = ya + c + (a - xb)
,我们用dis = sqrt(dx * dx + dy * dy)
更新答案。
所以这一部分的代码为:
//先经过前侧面
//情况1
dx = xa + yb;
dy = ya + c + xb;
ans = min(ans, calc(dx, dy));
//情况2
dx = (a - xa) + yb;
dy = ya + c + (a - xb);
ans = min(ans, calc(dx, dy));
先经过后侧面
最后是首先经过后侧面的情况。在这种情况下又分为两种情况,一种是上顶面-后侧面-左侧面-下底面;一种是后顶面-前侧面-右侧面-下底面。
首先是依次经过上顶面-后侧面-左侧面-下底面,我们将其展开:
这时横向距离dx = xa + (b - yb)
,纵向距离dy = (b - ya) + c + xb
,我们用dis = sqrt(dx * dx + dy * dy)
更新答案。
接着是依次经过上顶面-后侧面-后侧面-下底面的情况,我们也将其展开:
这时横向距离dx = (a - xa) + (b - yb)
,纵向距离dy = (b - ya) + c + (a - xb)
,我们用dis = sqrt(dx * dx + dy * dy)
更新答案。
所以这一部分的代码为:
//先经过后侧面
//情况1
dx = xa + (b - yb);
dy = (b - ya) + c + xb;
ans = min(ans, calc(dx, dy));
//情况2
dx = (a - xa) + (b - yb);
dy = dy = (b - ya) + c + (a - xb);
ans = min(ans, calc(dx, dy));
同样地,之所以我们只讨论了经过三个面和四个面的情况,是因为当面继续增多时,和讨论相邻面四类似的,两点之间的横向距离和纵向距离也是会增加的,这时就没有三或者四个面那么优了。所以对于对立面的点,只考虑经过三个面和四个面就已经足够啦。
算法模板
题目描述
我们还是沿用开篇时提到的那个问题:
[JROJ]对于一个给定的长方体(如下图所示),其沿着x轴的边长是a,沿着y轴的边长是b,沿着z轴的边长是c:
现在我们的小蒟蒻站在这个长方体表面上的任意一点A上,他的家在长方体表面上的另一点B点上。为了方便接下来的讨论,我们约定A点在长方体的上表面上。现在小蒟蒻想要沿着长方体的外表面从A点走到B点(如下图橙色路径为一条可行路径),给出A点和B点的坐标,请问他需要走过的最短距离是多少呢?
算法模板
算法的思路在上面已经说的很清楚啦,下面给出模板:
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
double a, b, c; //长方体的长宽高
double xa, ya, za; //A点的坐标
double xb, yb, zb; //B点的坐标
double ans; //存储计算答案
double dx, dy; //平面展开后A点和B点的坐标差
double calc(double x, double y) {
double ans = sqrt(x * x + y * y);
return(ans);
}//勾股定理计算
int main() {
//在这里我们约定za == c恒成立也就是A点一定在上表面
//在使用这个模板的时候如果A不在上表面就旋转一下
//让A成为长方体上表面上的点就好啦
scanf("%lf%lf%lf", &a, &b, &c);
scanf("%lf%lf%lf", &xa, &ya, &za);
scanf("%lf%lf%lf", &xb, &yb, &zb);
//A和B同在上表面(同一个面)的情况
if (zb == c) {
ans = sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb) + (za - zb) * (za - zb));
printf("%0.8lf\n", ans);
}
//A在上表面,B在侧面(相邻面)的情况
else if (xb == 0 || xb == a || yb == 0 || yb == b) {
if (xb == 0) {
//展开两个面
dx = xa + (c - zb);
dy = fabs(ya - yb);
ans = calc(dx, dy);
//展开三个面
//情况1
dx = xa + yb;
dy = ya + (c - zb);
ans = min(ans, calc(dx, dy));
//情况2
dx = xa + (b - yb);
dy = (b - ya) + (c - zb);
ans = min(ans, calc(dx, dy));
}
else if (xb == a) {
//展开两个面
dx = (a - xa) + (c - zb);
dy = fabs(ya - yb);
ans = calc(dx, dy);
//展开三个面
//情况1
dx = (a - xa) + yb;
dy = ya + (c - zb);
ans = min(ans, calc(dx, dy));
//情况2
dx = (a - xa) + (b - yb);
dy = (b - ya) + (c - zb);
ans = min(ans, calc(dx, dy));
}
else if (yb == 0) {
//展开两个面
dx = fabs(xa - xb);
dy = ya + (c - zb);
ans = calc(dx, dy);
//展开三个面
//情况1
dx = xa + (c - zb);
dy = ya + xb;
ans = min(ans, calc(dx, dy));
//情况2
dx = (a - xa) + (c - zb);
dy = ya + (a - xb);
ans = min(ans, calc(dx, dy));
}
else if (yb == b) {
//展开两个面
dx = fabs(xa - xb);
dy = (b - ya) + (c - zb);
ans = calc(dx, dy);
//展开三个面
//情况1
dx = xa + (c - zb);
dy = (b - ya) + xb;
ans = min(ans, calc(dx, dy));
//情况2
dx = (a - xa) + (c - zb);
dy = (b - ya) + (a - xb);
ans = min(ans, calc(dx, dy));
}
}
//A在上表面,B在底面(对立面)的情况
else {
//经过三个面
//经过左侧面
dx = xa + c + xb;
dy = fabs(ya - yb);
ans = calc(dx, dy);
//经过右侧面
dx = (a - xa) + c + (a - xb);
dy = fabs(ya - yb);
ans = min(ans, calc(dx, dy));
//经过前侧面
dx = fabs(xa - xb);
dy = ya + c + yb;
ans = min(ans, calc(dx, dy));
//经过后侧面
dx = fabs(xa - xb);
dy = (b - ya) + c +(b - yb);
ans = min(ans, calc(dx, dy));
//经过四个面
//先经过左侧面
//情况1
dx = xa + c + yb;
dy = ya + xb;
ans = min(ans, calc(dx, dy));
//情况2
dx = xa + c + (b - yb);
dy = (b - ya) + xb;
ans = min(ans, calc(dx, dy));
//先经过右侧面
//情况1
dx = (a - xa) + c + yb;
dy = ya + (a - xb);
ans = min(ans, calc(dx, dy));
//情况2
dx = (a - xa) + c + (b - yb);
dy = (b - ya) + (a - xb);
ans = min(ans, calc(dx, dy));
//先经过前侧面
//情况1
dx = xa + yb;
dy = ya + c + xb;
ans = min(ans, calc(dx, dy));
//情况2
dx = (a - xa) + yb;
dy = ya + c + (a - xb);
ans = min(ans, calc(dx, dy));
//先经过后侧面
//情况1
dx = xa + (b - yb);
dy = (b - ya) + c + xb;
ans = min(ans, calc(dx, dy));
//情况2
dx = (a - xa) + (b - yb);
dy = dy = (b - ya) + c + (a - xb);
ans = min(ans, calc(dx, dy));
}
printf("%0.4lf", ans);
return 0;
}
结语
通过这篇BLOG,相信你对长方形的展开又更加熟悉了。这也是第一次尝试插入这么多图片来帮助同学们理解,希望同学们能够喜欢。最后也希望你喜欢这篇BLOG!
tql!
木薯大大tql!!!