用C++暴力求出正方體中放置的最大正方形

前些天女朋友無聊刷知乎，刷到一個有趣的問題，拿這個來考我。本人數學不算好，但是儘力嘗試，算了許久都沒有算出來。但是作為一個計算機專業的大一寶寶，為什麼不能藉此機會體會一下暴力的美感呢。

原問題如下：

體積為1的正方體內，能放進的最大正方形面積是多少？ @謝大大

首先，面積最大的正方形一定經過正方體的體心。

令最大的正方形為 ，假設 不經過體心，則以體心為對稱中心做 的對稱圖形 ，也在正方體內部。兩兩連接 的四個頂點，得到一個柱體 ,此柱體的一個截面一定經過正方體體心。所以，面積最大的正方形中至少存在一個經過正方體體心，而由於正方形本身的對稱性，這個正方形的中心也必定是正方體的體心。

由於正方形的對角線相等並相互垂直平分，所以問題就轉化成 如何找到過正方體體心最長的一對相等的垂直平分線段。

然後，設其中一條對角線的一半為 ，在正方體上找到這一條線段：

則向量 為 ，設過 點平面 ，則 為 ，接著我們找出 平面與 三個平面的交線。將 代入 ，得到 。

然後我們要用代碼求出這個交線上離中心最遠的距離。

直接暴力即可。

#define STEP 0.001#define EPSILON 1e-5double dis(double a,double b,double c){ return sqrt(a*a+b*b+c*c);}double x_brane(double m,double n){ double re=0.0; double y; for(double z=-0.5;z<=0.5+EPSILON;z+=STEP) { y=-(z+m)/n/2.0; if(abs(y)<=0.5) { double t=dis(0.5,y,z); if(t>re) re=t; } } return re;}

同理求出 與其他兩個平面交線上離中心最遠的距離。

double y_brane(double m,double n){ double re=0.0; double z; for(double x=-0.5;x<=0.5+EPSILON;x+=STEP) { z=-2.0*m*x-n; if(abs(z)<=0.5) { double t=dis(x,0.5,z); if(t>re) re=t; } } return re;}double z_brane(double m,double n){ double re=0.0; double y; for(double x=-0.5;x<=0.5+EPSILON;x+=STEP) { y=-(m*x+0.25)/n; if(abs(y)<=0.5) { double t=dis(x,y,0.5); if(t>re) re=t; } } return re;}

得到三條交線離中心點最大的距離之後，在 與這個最大距離當中取最小值，得到的就是正方形對角線長度的一半，由此可求出正方形的面積。

然後對 進行枚舉，求出並記錄最大的情況即可。

int main(int argc, const char * argv[]) { double m=0,n=0; double ans=0; double ansm=0,ansn=0; for(m=0;m<=0.5+EPSILON;m+=STEP) for(n=0;n<=0.5+EPSILON;n+=STEP) { double this_egde=dis(m,n,0.5); double z=z_brane(m,n),x=x_brane(m,n),y=y_brane(m,n); printf("m=%.3lf, n=%.3lf, ",m,n); printf("x=%.3lf, y=%.3lf, z=%.3lf,",x,y,z); double max_edge=max(x,max(y,z)); printf(" s=%.3lf
",min(this_egde,max_edge)); if(ans { ans=min(this_egde,max_edge); ansm=m;ansn=n; } } cout<<ans<<" "<<(ans*ans)*2<<endl; printf("( %.3lf , %.3lf , %.3lf )
",ansm,ansn,0.5); return 0;}

最終結果：能放進的最大正方形面積為 1.125

各個頂點都在某條棱的1/4處，具體請看題圖。

本人學寫程序不久，水平有限，有錯誤或不足之處煩請各位大神指出，謝謝！

推薦閱讀：