多角形同士の被覆問題。

2003年3月の世界大会の問題。出場68チーム中、手をつけたのは1チーム、解いたのは0チーム。難問かも知れない。

情報処理学会にも こんな解答 が載っているが、参考になる?

Problem E
Covering Whole Holes
---- The 2003 ACM Programming Contest World Finals ----

Can you cover a round hole with a square cover? You can, as long as the square cover is big enough. It obviously will not be an exact fit, but it is still possible to cover the hole completely.
 「四角いカバーで丸いホール(穴)をカバーできるか。四角いカバーが十分に大きければOKと答えるだろう。ピッタリ合わせるには難しいが、完全にカバーすることは可能だろう。」

The Association of Cover Manufacturers (ACM) is a group of companies that produce covers for all kinds of holes --- manholes, holes on streets, wells, ditches, cave entrances, holes in backyards dug by dogs to bury bones, to name only a few. ACM wants a program that determines whether a given cover can be used to completely cover a specified hole. At this time, they are interested only in covers and holes that are rectangular polygons (that is, polygons with interior angles of only 90 or 270 degrees). Moreover, both cover and hole are aligned along the same coordinate axes, and are not supposed to be rotated against each other --- just translated relative to each other.
 「ACMはあらゆるホールのカバーをつくる企業集団だ。ACMはホールを完全にカバーできるかどうかを判断してくれるプログラムを必要としている。いまの時点では、カバーもホールも直角をなす多角形(つまり多角形の各内角は90度か270度)だけのものと考えていい。さらに、カバーもホールも座標の軸線に沿って並んでいる。また、互いに回転することはしない。平行移動だけで考えてほしい。」

Input
The input consists of several descriptions of covers and holes. The first line of each description contains two integers h and c (4<=h<=50 and 4<=c<=50), the number of points of the polygon describing the hole and the cover respectively. Each of the following h lines contains two integers x and y, which are the vertices of the hole's polygon in the order they would be visited in a trip around the polygon. The next c lines give a corresponding description of the cover. Both polygons are rectangular, and the sides of the polygons are aligned with the coordinate axes. The polygons have positive area and do not intersect themselves.
 「入力に複数のカバーとホールの説明が入る。各説明の1行目には整数2つ、hとc (4<=h<=50、4<=c<=50) が、それぞれホールとカバーの多角形頂点の数を表す。その後に続くh行に整数2つ、xとyが入る。それらは多角形に沿った順番で現われるホールの頂点を示す。そのつぎのc行は対応したカバーの頂点だ。両方の多角形はともに直角をなし、多角形の各辺が座標軸線上にのっている。それぞれの多角形は正の面積をもち、内部で横切ることはない。」

The last description is followed by a line containing two zeros.
 「入力の最後に0が2つ入る。」

Output
For each problem description, print its number in the sequence of descriptions. If the hole can be completely covered by moving the cover (without rotating it), print "Yes" otherwise print "No". Recall that the cover may extend beyond the boundaries of the hole as long as no part of the hole is uncovered. Follow the output format in the example given below.
 「各説明に対し、説明の番号を表示すること。カバーを回転せず移動だけでホールを完全にカバーすることができれば"Yes"と表示すること。そうできなければ"No"と表示すること。ホールをカバーしている限り、ホールの境界線からはみだしてカバーを動かせることに留意。

Sample Input
4 4
0 0
0 10
10 10
10 0
0 0
0 20
20 20
20 0
4 6
0 0
0 10
10 10
10 0
0 0
0 10
10 10
10 1
9 1
9 0
0 0

Output for the Sample Input
Hole 1: Yes
Hole 2: No

Comments are closed.

Post Navigation