《试题十 天然气的管道连接问题.doc》由会员分享，可在线阅读，更多相关《试题十 天然气的管道连接问题.doc（3页珍藏版）》请在金锄头文库上搜索。
1、试题十 天然气的管道连接问题如今使用天然气的人越来越多，作为天然气的供应商如何向用户供气，即如何使用户之间连接成一个树形网络是很重要的。一般来说，我们假设任意两个用户之间存在直线道相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。表1给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用天然气的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。 请您判
2、定表1中那些用户为有效用户。 请您设计一个算法将有效用户连接起来，并且连接的距离总和最小。表1：若干个可能的用户的地址的横纵坐标可能的用户的序号可能的用户横坐标可能的用户纵坐标可能的用户的序号可能的用户横坐标可能的用户纵坐标195.012958.27922620.276597.0845223.113942.34962719.872299.0083360.684351.55122860.379278.8862448.598233.39512927.218843.8659589.129943.29073019.881449.8311676.209722.5950311.527421.3963745
3、.646857.98073274.678664.349281.850476.03653344.509632.0036982.140752.98233493.181596.00991044.470364.05263546.599472.66321161.543220.90693641.864941.19531279.193737.98183784.622174.45661392.181378.33293852.515226.79471473.820768.08463920.264743.99241517.626646.10954067.213793.33801640.570656.7829418
4、3.811868.33321793.547079.4211421.964021.25601891.69045.91834368.127783.92381941.027060.28694437.948162.87852089.36505.02694583.179613.3773215.789141.53754650.281320.71332235.286830.49994770.947160.71992381.316687.43674842.889262.9888240.98611.50094930.461737.04772513.889176.79505018.965457.51485119.
5、343145.14257670.274067.56455268.22234.38957754.657169.92135330.27642.71857844.488072.75095454.167431.26857969.456747.83845515.08731.28638062.131055.48425669.789838.39678179.482112.10475737.837368.31168295.684345.07545886.00129.28428352.259071.58835985.36553.53388488.014289.28426059.356361.23958517.2
6、95627.31026149.655260.85408697.974725.47696289.97691.57608727.144786.56036382.16291.63558825.232923.23506464.491019.00758987.574280.48726581.797458.69189073.730690.83986666.02285.75819113.651923.18946734.197136.7568921.175723.93136828.972663.14519389.38984.97546934.119471.76349419.91387.83847053.407
7、969.26699529.872364.08157172.71138.40799666.144319.08877230.929045.43559728.440984.38697383.849644.18289846.922417.39007456.807235.3250996.478117.07937537.041415.360610098.833599.4295表2障碍区域1必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标13.206012.9166217.457119.337734.757620表3障碍区域2必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标15030253.746548.4490346.922257.1195433.320739.8050543.112356.3187表4障碍区域3必须要覆盖的点的坐标 表5障碍区域4必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标顶点序号顶点的横坐标顶点的纵坐标154.69827019075253.74659028095346.92228037080
