再帰的に定義された図形の距離算出の問題。

Problem C
Riding the Bus
---- The 2003 ACM Programming Contest World Finals ----

The latest research in reconfigurable multiprocessor chips focuses on the use of a single bus that winds around the chip. Processor components, which can be anywhere on the chip, are attached to connecting points on the bus so that they can communicate with each other.
 「マルチプロセッサ・チップの部品配置に関する最新研究として、チップ上に走るバスの使い方に焦点が当てられている。プロセッサの部品が、チップのどこにも配置可能だが、バスの接続点と繋いでおかないといけない。それで互いに通信可能になるのだ。」

Some research involves bus layout that uses recursively-defined “SZ” curves, also known as “S-shaped Peano curves.” Two examples of these curves are shown below. Each curve is drawn on the unit square. The order-1 curve, shown on the left, approximates the letter “S” and consists of line segments connecting the points (0,0), (1,0), (1,0.5), (0,0.5), (0,1), and (1,1) in order. Each horizontal line in an “S” or “Z” curve is twice as long as each vertical line. For the order-1 curve, the length of a vertical line, len, is 0.5.
 「ある研究に、再帰的に定義される"SZ"カーブのバスレイアウトが必要としている。下図にこういう形のカーブの例を2つ示した。カーブは単位正方形に書かれる。左側の1次カーブ、文字"S"に似ていて、点 (0,0), (1,0), (1,0.5), (0,0.5), (0,1), 及び (1,1) を繋ぐ線分で構成される。"S"あるいは"Z"カーブにある水平の線は縦の線の2倍の長さ。1次カーブでは、縦の線の長さlenは0.5となる。」

The order-2 curve, shown on the right, contains 9 smaller copies of the order-1 curve (4 of which are reversed left to right to yield “Z” curves). These copies are connected by line segments of length len, shown as dotted lines. Since the width and height of the order-2 curve is 8 x len, and the curve is drawn on the unit square, len = 0.125 for the order-2 curve.
 「右側に示した2次カーブは、1次カーブの縮小した9つのコピーを含む(うちの4つは左右反転していて、"Z"カーブの形をしている。)これらは長さlenの線分によって繋ぎ、ドットで図に示した。2次カーブは横幅と高さが8xlen、カーブが単位正方形に書かれているので、len=0.125。」

The order-3 curve contains 9 smaller copies of the order-2 curve (with 4 reversed left to right), connected by line segments, as described for the order-2 curve. Higher order curves are drawn in a similar manner. The connecting points to which processor components attach are evenly spaced every len units along the bus. The first connecting point is at (0,0) and the last is at (1,1). There are 9k connecting points along the order-k curve, and the total bus length is (9k-1)xlen units.
 「3次カーブは2次カーブの縮小したコピー9つからなり(うちの4つは左右逆転)、線分によって繋ぐ。高次カーブは同じ手法で書くことができる。プロセッサ部品のつなぐ接続点とはバス上のlen単位で等分した点のこと。最初の接続点は(0,0)、最後の点は(1,1)。k次カーブに9k個の接続点があり、バスの総長は(9k-1)xlen単位。」

You must write a program to determine the total distance that signals must travel between two processor components. Each component's coordinates are given as an x, y pair, 0<=x<=1 and 0<=y<=1, where x is the distance from the left side of the chip, and y is the distance from the lower edge of the chip. Each component is attached to the closest connecting point by a straight line. If multiple connecting points are equidistant from a component, the one with the smallest x coordinate and smallest y coordinate is used. The total distance a signal must travel between two components is the sum of the length of the lines connecting the components to the bus, and the length of the bus between the two connecting points. For example, the distance between components located at (0.5, 0.25) and (1.0, 0.875) on a chip using the order-1 curve is 3.8750 units.
 「プログラムを書いて、プロセッサ部品2つの間に伝わる信号の総距離を算出して欲しい。部品の座標はx, yペアで与えられ、0<=x<=1、 0<=y<=1。x はチップの左側からの距離、y は下側からの距離。各部品は直線で最寄の接続点に繋ぐ。部品から等距離の接続点が複数ある場合は、最小のx と最小のyの点を使う。部品間、信号の伝わる総距離とは、部品からバスの接続点までの距離の和と、2つの接続点間のバスの長さの合計距離だ。例えば、(0.5, 0.25) および (1.0, 0.875) に配置された部品間の距離は、1次カーブでは3.8750となる。」
 
Input
The input contains several cases. For each case, the input consists of an integer that gives the order of the SZ curve used as the bus (no larger than 8), and then four real numbers x1, y1, x2, y2 that give the coordinates of the processor components to be connected. While each processor component should actually be in a unique location not on the bus, your program must correctly handle all possible locations.
 「入力に複数のケースが含まれる。各ケースにおいて、整数1つ、SZカーブの次元(オーダー、最大8まで)を示すもの、実数4つ、x1, y1, x2, y2、繋ぐべくプロセッサ部品の座標を示すもの、が入る。プロセッサ部品はバス上にあってはいけないが、プログラムは可能な位置をすべて取り扱えるようにすること。」

The last case in the input is followed by a single zero.
 「入力の最後に0が入る。」

Output
For each case, display the case number (starting with 1 for the first case) and the distance between the processor components when they are connected as described. Display the distance with 4 digits to the right of the decimal point.
 「各々のケースについて、ケース番号(case number)(最初のケースは1として)および部品間の距離を入れること。距離は小数点以下4桁で表示すること。」

Use the same format as that shown in the sample output shown below. Leave a blank line between the output lines for consecutive cases.
 「出力フォーマット例を利用すること。各ケースの間に空白行を入れること。」

Sample Input
1 0.5 .25 1 .875
1 0 0 1 1
2 .3 .3 .7 .7
2 0 0 1 1
0

Output for the Sample Input
Case 1. Distance is 3.8750

Case 2. Distance is 4.0000

Case 3. Distance is 8.1414

Case 4. Distance is 10.0000

Comments are closed.

Post Navigation