Parallelepiped walk

发布于 2020-10-26  0 次阅读


题目大意:

在一个三维空间中,有一个长宽高分别为l,w,h的矩形,上面有A,B两点,求两点在表面间的最短距离

思路:

将A等效翻转到底面
试着将图形通过翻转的方式展开,每个方向最多两次即可求得答案

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
// #define TDS_ACM_LOCAL
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
inline int read(){
    register int x=0, f=0;
    register char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return f?-x:x;
}
inline void write(register int x){     
    if(x < 0) {putchar('-');x = -x;}        
    if(x > 9)  write(x/10);
    putchar(x % 10 + '0');
}

int ans;
void walk(int i, int j, int x0, int y0, int x, int y, int z, int l, int w, int h)
{
    if (z == 0)
        ans = min((x0 - x) * (x0 - x) + (y0 - y) * (y0 - y), ans);
    else
    {
        if (i >= 0 && i < 2)    // 右下翻
            walk(i + 1, j, x0, y0 - w, x, z, w - y, l, h, w);
        if (i <= 0 && i > -2)   // 左下翻
            walk(i - 1, j, x0, y0 + h, x, h - z, y, l, h, w);
        if (j >= 0 && j < 2)    // 里翻
            walk(i, j + 1, x0 - l, y0, z, y, l - x, h, w, l);
        if (j <= 0 && j > -2)   // 外翻
            walk(i, j - 1, x0 + h, y0, h - z, y, x, h, w, l);
    }
}

void solve()
{
    int l, w, h, x1, y1, z1, x2, y2, z2;
    while (scanf("%d%d%d", &l, &w, &h) != EOF)
    {
        scanf("%d%d%d", &x1, &y1, &z1);
        scanf("%d%d%d", &x2, &y2, &z2);
        // 通过等效翻转,将A点所在面翻转到底面
        // 判断A是否在上下面
        if (z1 != 0 && z1 != h)
        {
            // 判断A是否在左右面
            if (y1 != 0 && y1 != w)
            {
                swap(x1, z1);
                swap(x2, z2);
                swap(l, h);
            }
            else
            {
                swap(y1, z1);
                swap(y2, z2);
                swap(w, h);
            }
        }
        if (z1 == h)
        {
            z1 = 0;
            z2 = h - z2;
        }
        ans = INF;
        walk(0, 0, x1, y1, x2, y2, z2, l, w, h);
        printf("%d\n", ans);
    }
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

平平无奇的大学在读本科生