📄 ccorners.html
字号:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=gb2312">
<META NAME="GENERATOR" CONTENT="Mozilla/4.03 [zhcn] (Win95; I) [Netscape]">
<TITLE>1996 ACM Finals, Problem C - Cutting Corners</TITLE>
<!SGML "ISO 8879:1986">
</HEAD>
<BODY BGCOLOR="#FFFFFF">
<HR NOSHADE>
<CENTER>
<H1>
1996 ACM Scholastic Programming Contest Finals</H1></CENTER>
<CENTER>
<H4>
sponsored by Microsoft</H4></CENTER>
<CENTER>
<H1>
Problem C</H1></CENTER>
<CENTER>
<H2>
Cutting Corners</H2></CENTER>
<CENTER>
<H3>
Input file: corner.in</H3></CENTER>
Bicycle messengers who deliver documents and small items to businesses
have long been part of the guerrilla transportation services in several
major U.S. cities. The cyclists of Boston are a rare breed of riders. They
are notorious for their speed, their disrespect for one-way streets and
traffic signals, and their brazen disregard for cars, taxis, buses, and
pedestrians.
<P>Bicycle messenger services are very competitive. Billy's Bicycle Messenger
Service is no exception. To boost its competitive edge and to determine
its actual expenses, BBMS is developing a new scheme for pricing deliveries
that depends on the shortest route messengers can travel. You are to write
a program to help BBMS determine the distances for these routes.
<P>The following assumptions help simplify your task:
<UL>
<LI>
Messengers can ride their bicycles anywhere at ground level except inside
buildings.</LI>
<LI>
Ground floors of irregularly shaped buildings are modeled by the union
of the interiors of rectangles. By agreement any intersecting rectangles
share interior space and are part of the same building.</LI>
<LI>
The defining rectangles for two separate buildings never touch, although
they can be quite close. (Bicycle messengers- skinny to a fault-can travel
between any two buildings. They can cut the sharpest corners and run their
skinny tires right down the perimeters of the buildings.)</LI>
<LI>
The starting and stopping points are never inside buildings.</LI>
<LI>
There is always some route from the starting point to the stopping point.</LI>
</UL>
Your program must be able to process several scenarios. Each scenario defines
the buildings and the starting and stopping points for a delivery route.
The picture below shows a bird's-eye view of a typical scenario.
<CENTER></CENTER>
<CENTER><IMG SRC="corner1.gif" ></CENTER>
<P>The input file represents several scenarios. Input for each scenario
consists of lines as follows:
<DL>
<DT>
First line: <I>n</I></DT>
<DD>
The number of rectangles describing the buildings in the scenario. 0 <=
<I>n</I> <= 20</DD>
<DT>
Second line: <I>x<SUB>1</SUB> y<SUB>1</SUB> x<SUB>2</SUB> y<SUB>2</SUB></I></DT>
<DD>
The x- and y-coordinates of the starting and stopping points of the route.</DD>
<DT>
Remaining <I>n</I> lines: <I>x<SUB>1</SUB> y<SUB>1</SUB> x<SUB>2</SUB>
y<SUB>2</SUB> x<SUB>3</SUB> y<SUB>3</SUB></I></DT>
<DD>
The x- and y-coordinates of three vertices of a rectangle.</DD>
</DL>
The x- and y-coordinates of all input data are real numbers between 0 and
1000 inclusive. Successive coordinates on a line are separated by one or
more blanks. The integer -1 follows the data of the last scenario.
<P>Output should number each scenario (Scenario #1, Scenario #2, etc.)
and give the distance of the shortest route from starting to stopping point
as illustrated in the Sample Output below. The distance should be written
with two digits to the right of the decimal point. Output for successive
scenarios should be separated by blank lines.
<H3>
<HR>Sample Input</H3>
<PRE>5
6.5 9 10 3
1 5 3 3 6 6
5.25 2 8 2 8 3.5
6 10 6 12 9 12
7 6 11 6 11 8
10 7 11 7 11 11
-1</PRE>
<H3>
<HR>Sample Output</H3>
<PRE>Scenario #1
route distance: 7.28</PRE>
<HR NOSHADE>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -