#P1249. Oil Pipeline
Oil Pipeline
本题没有可用的提交语言。
题目描述
洛基石油公司(Rocky Oil)拥有几块矩形的油田,正在这些油田中钻探新油井。公司希望使用南北走向的直管道,将油田中的所有油井连接到一条东西走向的单一管道上。你的任务是编写一个程序,首先找到东西走向管道的位置,使得油田中南北走向管道的总长度最短;然后,如果可能的话,绘制出该油田的地图。
每块矩形油田在东西方向上长94个单位,在南北方向上长73个单位。该区域使用整数坐标,西南角的坐标为(1,1),东北角的坐标为(94,73)。油井可以位于该区域内的任何整数坐标位置,且所有油井的位置都不相同。东西走向的管道将在一个整数的南北坐标位置上横跨整个油田。具有相同东西坐标的油井共用同一根管道。如果存在多个位置能使东西走向管道达到相同的最短总长度,则始终选择最靠南的位置(即南北坐标值最低的位置)。
考虑下面的第一个输入示例。当东西走向管道位于南北坐标为11的位置时,东西坐标为1的油井在管道上,其连接管道长度为零。东西坐标为69的两口油井可以共用一根长度为18的管道。这三口油井的总管道长度为18。如果东西走向管道位于南北坐标为20的位置,将会有两根南北走向的管道,一根在坐标1处长度为9,另一根在坐标69处长度为9,总长度同样为18。实际上,任何位于南北坐标11到20之间的东西走向管道,总长度都为18,这是最短的长度。由于存在多个使总长度最小的管道位置,所以选择最靠南的位置,即11。
绘制的任何地图必须最多占用69列和19行(不包括边框和标签),以便能在标准尺寸的显示器上显示。地图必须包括东西走向的管道、所有油井以及所有南北走向的管道。只应绘制实际包含油井的那部分油田,使用最小的边界矩形,其边缘是5的倍数。无论地图的宽度如何,东西走向的管道都必须横跨整个地图。油井必须位于边界矩形内部,而不是在其任何边缘上。这些限制条件可能会导致某些油田无法绘制地图。第一个输入示例展示了可能的最大地图。
输入
输入由一个或多个油田的数据组成,然后是一行包含0 0的内容,表示输入结束。每个油田的数据由一个或多个正整数对组成,每对整数占一行,表示油田中油井的位置。整数对-1 -1表示一个油田数据的结束。
输出
对于每个油田,先输出一行带有编号的标题。然后,如果可能的话,输出该油田的地图。否则,输出一个句子,说明管道的位置。请使用下面所示的确切格式。
使用“@”表示油井,“*”表示管道,“.”(一个点)表示空的网格位置。油井的显示优先于管道,所以如果油井和管道位于同一位置,则使用“@”。在绘制的油田地图周围绘制边框,使用“|”(竖线)表示南北方向的边缘,使用“-”(横线)表示东西方向的边缘,但每隔5个网格位置用“+”标记,如示例所示。用其在油田中的位置标记每个“+”。每个南北方向“+”的标记紧跟在“+”符号之前。最北边的“+”的标记必须从输出的第一行开头开始。东西方向“+”的标记的最高位数字必须始终在“+”的正下方。与通常的输出约定不同,地图中的某些行可能会有前导空格。
输入示例 1
1 11
69 29
69 20
-1 -1
35 35
-1 -1
1 1
94 73
1 73
94 1
-1 -1
2 2
3 7
4 4
6 1
-1 -1
0 0
输出示例 1
OIL FIELD 1
30+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|....................................................................@|
|....................................................................*|
|....................................................................*|
|....................................................................*|
25+....................................................................*+
|....................................................................*|
|....................................................................*|
|....................................................................*|
|....................................................................*|
20+....................................................................@+
|....................................................................*|
|....................................................................*|
|....................................................................*|
|....................................................................*|
15+....................................................................*+
|....................................................................*|
|....................................................................*|
|....................................................................*|
|@********************************************************************|
10+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70
OIL FIELD 2
40+----+----+
|.........|
|.........|
|.........|
|.........|
35+****@****+
|.........|
|.........|
|.........|
|.........|
30+----+----+
30 35 40
OIL FIELD 3
Map is too big to draw for pipeline at 1
OIL FIELD 4
10+----+----+
|.........|
|.........|
|..@......|
|..*......|
5+..*......+
|..*@.....|
|..**.....|
|*@*******|
|.....@...|
0+----+----+
0 5 10