多角形の中に入れる最大円を探し出すプログラム。

Problem B
Heliport
—- The 2004 ACM Programming Contest World Finals —-

In these fast-paced times, companies are investing in heliports to reduce travel time for their busy executives. The heliports are typically circular landing pads, constructed on the roofs of the companies’ headquarters. You must write a program that finds the largest radius for a circular heliport that can be constructed on the flat roof of a building that is in the form of a simple polygon. Since this is merely the design phase of the construction effort, your program must find only the radius of the heliport. The maximum radius for a heliport in the diagram shown is 10.
 「あっという間に時間が過ぎていく今日、多忙な役員達の移動時間を節約するため、会社はヘリポートへの投資を行っている。ヘリポートは一般的に円状の離着陸場であり、本社の屋上に建てられる。単純多角形の形をしている平らなビルの屋上に、円状ヘリポートを建設するよう、最大半径を見つけ出すプログラムを書いて欲しい。建設の設計段階にすぎないので、プログラムはヘリポートの半径を見つけ出すだけでよい。図に示したヘリポートの最大半径は10である。」

Input File
The input file contains several test cases. Each test case consists of two lines. The first line consists of an even integer n (4<=n<=20), which is the number of the sides of the building. The second line consists of n pairs of the form (m, d), where m is an integer (1<=m<=50) and d is a letter (U, R, D, L). Assuming the roof is drawn on the Cartesian plane, m is the length of a roof boundary segment and d is the direction of that segment as you travel counterclockwise around the roof. U, R, D, and L mean “Up,” “Right,” “Down,” and “Left。” respectively. The boundary segments of the roof, which are parallel to the x and y axes, are given in counterclockwise order. The starting position is the origin (0, 0). Input for the last test case is followed by a line consisting of the number 0.
 「入力ファイルに複数のテストケースが含まれる。各々のテストケースは2行を含む。1行目には偶数である整数 n (4<=n<=20)が入り、ビルの辺の数を表す。2行目には、n個の(m, d)ペアが入る。m ((1<=m<=50)は整数、dは文字(U, R, D, L)のどれか。屋上はデカルト平面に描かれ、mは屋上の端を表す線分の長さ、dは屋上を反時計回りで見たときの線分の方向を表す。U, R, D, Lはそれぞれ、上、右、下、左を示す。屋上の端となる線分は、x, y 軸と平行していて、反時計方向の順で与えられ、原点(0, 0)から始まる。入力の最後に数字0の行が入る。」

Output File
For each test case, the output consists of a separate line containing the case number (starting with 1) and a real number (rounded to two digits after the decimal point) representing the radius of the heliport. Print a blank line between cases as shown in the sample output.
 「各テストケースに対し、ケース番号(1からスタート)、およびヘリポートの半径を示す実数(小数点右2桁まで)をぞれぞれの行に出力すること。サンプル出力にあるように、テストケースの間に空白行を入れること。」

Sample Input
4
2 R 2 U 2 L 2 D
10
10 R 10 U 10 L 10 U 10 R 5 U 30 L 20 D 20 R 5 D
0

Output for the Sample Input
Case Number 1 radius is: 1.00

Case Number 2 radius is: 10.00

Comments are closed.

Post Navigation