UVa 13027 - Moroccan Wooden Box

Source

An Asian Preliminary Regional(20151205)
(ICPC Dhaka 2015 Preliminary)
UVa 13027

問題概要

半径 $R$ の球を $k$ 個($k=7,8$)だけ箱のなかに詰めたい.
箱の内部の高さは $2R$ で,縦と横は自由に長さを変えられるが,正方形(縦の長さと横の長さは一致)でなければならない.
箱の内部はそうで,箱自体は,その周り $6$ 方向が,幅 $W$ の木で囲まれた直方体の形をしている.
球を詰める際,rigidでなければならない,つまり,蓋をした後,どちらの方向に傾けても,球が動いてはいけない.
箱の最大の体積を $k=7$ の場合と $k=8$ の場合に求める問題.
問題文中にどのように詰めれば良いかというのが図示されている.

解法

結局のところ,半径 $1$ の円をrigidに正方形に詰めた時,正方形の長さがいくらになるかを求めてやれば,後は簡単な算数で答えが求まる.
問題文中の図を頼りに,各円の中心座標と,正方形の一辺の長さを変数に,接していると思われる円同士の中心間の距離とか,正方形と接している円についての座標の式などを立ててやって,Mapleのfsolveを使って解いて,結果を埋め込んだ.
単純にやるとなかなか正しい答えが求まらなかったが,適当に変数の範囲を制限してあげたり,試行錯誤すると正しい答えが求まる.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年09月25日11時30分01秒
Last modified: 2015年12月16日00時57分11秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151205_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: