仓库路线设计.doc 2页

此文档收集于网络，如有侵权，请联系网站删除仓库路线设计●问题描述 　　ACK是一家以生产计算机及其外设产品为主的高科技企业。不仅ACK的产品在国内领先，而且它的仓库设计也独具特色。由于生产的产品多种多样，ACK的仓库是由若干个大小不等、形状各异的子仓库组成，每个仓库有一个入口（也是出口），坐标为。由于有些产品是互相关联的，所以某些仓库的入口之间通过地下通道相联。（0，0）是地下通道的入口处。每次装卸货物时，仓库的运输车都要从（0，0）处进入地下通道，在通道中行驶一段距离后进入到某一子仓库中装卸货物。但是最近运输车出现了一点小毛病，那就是运输车只能右转弯，而不能左转弯。这对运输车在仓库中运输货物并没有什么影响，但是由于地下通道的宽度有限，运输车转弯的角度不能超过180。在这种情况下，某些仓库仍然是可到达的，但是有些仓库却是根本不能到达的。例如在如上图)。 　　例子中，如果运输车的行驶路线为O-B-D-E-F-B-A（这条路线保证了运输车不进行左转弯），则可依次到达子仓库B、D、E、F、A，但是无论运输车如何选择其他的路线，子仓库C都是不能到达的。 　　作为ACK的高级工程师，请你编程找出从O点可以到达的所有子仓库。 　　注意：为保持仓库的清洁，地下通道采用"管道"的形式（除入口和出口以外都是封闭的），所以即使仓库i和仓库j相连，仓库k的坐标为在和的连线上，当运输车在从仓库i到仓库j的路线上时仍不能到达仓库k。 　　●数据输入：输入数据由line.in提供。文件的第一行为一个整数N（N≤200），表示共有N个子仓库。从第二行开始到第(N+1)行每行有两个数(-50≤xi,yi≤50)，表示第i个仓库的坐标。然后是一个整数M(M≤100)，表示共有M条路线。接下来的M行每行有两个整数P、Q，表示子仓库P和子仓库Q有通道相连，在这里通道是双向的，即如果P可以和Q相连，那么Q也一定和P相连。其中仓库的入口（0，0）用0表示。 　　●结果输出：将可能到达的子仓库序号按升序输出到文件line.out中。输入文件中给出的数据保证至少有一个可达子仓库。　　●输入输出样例此文档仅供学习与交流 此文档收集于网络，如有侵权，请联系网站删除输入文件样例输出文件样例line.inline.out6 04 12 24 23 32 21 8 02 12 14 24 34 45 56 2612456 此文档仅供学习与交流