求助"天然气的管道连接问题"

yuanzhen8786

如今使用天然气的人越来越多，作为天然气的供应商如何向用户供气，即如何使用户之间连接成一个树形网络是很重要的。一般来说，我们假设任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。
表1给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用天然气的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。
表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。
（1）请您判定表1中那些用户为有效用户。
（2）请您设计一个算法将有效用户连接起来，并且连接的距离总和最小。
表1  若干个可能的用户的地址的横纵坐标
可能的用户的序号        可能的用户横坐标        可能的用户纵坐标
1.0000        95.0129        58.2792
2.0000        23.1139        42.3496
3.0000        60.6843        51.5512
4.0000        48.5982        33.3951
5.0000        89.1299        43.2907
6.0000        76.2097        22.5950
7.0000        45.6468        57.9807
8.0000        1.8504        76.0365
9.0000        82.1407        52.9823
10.0000        44.4703        64.0526
11.0000        61.5432        20.9069
12.0000        79.1937        37.9818
13.0000        92.1813        78.3329
14.0000        73.8207        68.0846
15.0000        17.6266        46.1095
16.0000        40.5706        56.7829
17.0000        93.5470        79.4211
18.0000        91.6904        5.9183
19.0000        41.0270        60.2869
20.0000        89.3650        5.0269
21.0000        5.7891        41.5375
22.0000        35.2868        30.4999
23.0000        81.3166        87.4367
24.0000        0.9861        1.5009
25.0000        13.8891        76.7950
26.0000        20.2765        97.0845
27.0000        19.8722        99.0083
28.0000        60.3792        78.8862
29.0000        27.2188        43.8659
30.0000        19.8814        49.8311
31.0000        1.5274        21.3963
32.0000        74.6786        64.3492
33.0000        44.5096        32.0036
34.0000        93.1815        96.0099
35.0000        46.5994        72.6632
36.0000        41.8649        41.1953
37.0000        84.6221        74.4566
38.0000        52.5152        26.7947
39.0000        20.2647        43.9924
40.0000        67.2137        93.3380
41.0000        83.8118        68.3332
42.0000        1.9640        21.2560
43.0000        68.1277        83.9238
44.0000        37.9481        62.8785
45.0000        83.1796        13.3773
46.0000        50.2813        20.7133
47.0000        70.9471        60.7199
48.0000        42.8892        62.9888
49.0000        30.4617        37.0477
50.0000        18.9654        57.5148
51.0000        19.3431        45.1425
52.0000        68.2223        4.3895
53.0000        30.2764        2.7185
54.0000        54.1674        31.2685
55.0000        15.0873        1.2863
56.0000        69.7898        38.3967
57.0000        37.8373        68.3116
58.0000        86.0012        9.2842
59.0000        85.3655        3.5338
60.0000        59.3563        61.2395
61.0000        49.6552        60.8540
62.0000        89.9769        1.5760
63.0000        82.1629        1.6355
64.0000        64.4910        19.0075
65.0000        81.7974        58.6918
66.0000        66.0228        5.7581
67.0000        34.1971        36.7568
68.0000        28.9726        63.1451
69.0000        34.1194        71.7634
70.0000        53.4079        69.2669
71.0000        72.7113        8.4079
72.0000        30.9290        45.4355
73.0000        83.8496        44.1828
74.0000        56.8072        35.3250
75.0000        37.0414        15.3606
76.0000        70.2740        67.5645
77.0000        54.6571        69.9213
78.0000        44.4880        72.7509
79.0000        69.4567        47.8384
80.0000        62.1310        55.4842
81.0000        79.4821        12.1047
82.0000        95.6843        45.0754
83.0000        52.2590        71.5883
84.0000        88.0142        89.2842
85.0000        17.2956        27.3102
86.0000        97.9747        25.4769
87.0000        27.1447        86.5603
88.0000        25.2329        23.2350
89.0000        87.5742        80.4872
90.0000        73.7306        90.8398
91.0000        13.6519        23.1894
92.0000        1.1757        23.9313
93.0000        89.3898        4.9754
94.0000        19.9138        7.8384
95.0000        29.8723        64.0815
96.0000        66.1443        19.0887
97.0000        28.4409        84.3869
98.0000        46.9224        17.3900
99.0000        6.4781        17.0793
100.0000        98.8335        99.4295
表2障碍区域1必须要覆盖的点的坐标
顶点序号        顶点的横坐标        顶点的纵坐标
1        3.2060        12.9166
2        17.4571        19.3377
3        4.7576        20
表3障碍区域2必须要覆盖的点的坐标
顶点序号        顶点的横坐标        顶点的纵坐标
1        50        30
2        53.7465        48.4490
3        46.9222        57.1195
4        33.3207        39.8050
5        43.1123        56.3187
表4障碍区域3必须要覆盖的点的坐标
顶点序号        顶点的横坐标        顶点的纵坐标
1        54.6982        70
2        53.7465        90
3        46.9222        80
表5障碍区域4必须要覆盖的点的坐标
顶点序号        顶点的横坐标        顶点的纵坐标
1        90        75
2        80        95
3        70        80