如今使用天然气的人越来越多，作为天然气的供应商如何向用户供气，即如何使用户之间连接成一个树形网络是很重要的。一般来说，我们假设任意两个用户之间存在直线道相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。
表1给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用天然气的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。
表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。
⑴ 请您判定表1中那些用户为有效用户。
⑵ 请您设计一个算法将有效用户连接起来，并且连接的距离总和最小。
表1：若干个可能的用户的地址的横纵坐标
|
可能的用户的序号 |
可能的用户横坐标 |
可能的用户纵坐标 |
可能的用户的序号 |
可能的用户横坐标 |
可能的用户纵坐标 |
|
1 |
95.0129 |
58.2792 |
26 |
20.2765 |
97.0845 |
|
2 |
23.1139 |
42.3496 |
27 |
19.8722 |
99.0083 |
|
3 |
60.6843 |
51.5512 |
28 |
60.3792 |
78.8862 |
|
4 |
48.5982 |
33.3951 |
29 |
27.2188 |
43.8659 |
|
5 |
89.1299 |
43.2907 |
30 |
19.8814 |
49.8311 |
|
6 |
76.2097 |
22.5950 |
31 |
1.5274 |
21.3963 |
|
7 |
45.6468 |
57.9807 |
32 |
74.6786 |
64.3492 |
|
8 |
1.8504 |
76.0365 |
33 |
44.5096 |
32.0036 |
|
9 |
82.1407 |
52.9823 |
34 |
93.1815 |
96.0099 |
|
10 |
44.4703 |
64.0526 |
35 |
46.5994 |
72.6632 |
|
11 |
61.5432 |
20.9069 |
36 |
41.8649 |
41.1953 |
|
12 |
79.1937 |
37.9818 |
37 |
84.6221 |
74.4566 |
|
13 |
92.1813 |
78.3329 |
38 |
52.5152 |
26.7947 |
|
14 |
73.8207 |
68.0846 |
39 |
20.2647 |
43.9924 |
|
15 |
17.6266 |
46.1095 |
40 |
67.2137 |
93.3380 |
|
16 |
40.5706 |
56.7829 |
41 |
83.8118 |
68.3332 |
|
17 |
93.5470 |
79.4211 |
42 |
1.9640 |
21.2560 |
|
18 |
91.6904 |
5.9183 |
43 |
68.1277 |
83.9238 |
|
19 |
41.0270 |
60.2869 |
44 |
37.9481 |
62.8785 |
|
20 |
89.3650 |
5.0269 |
45 |
83.1796 |
13.3773 |
|
21 |
5.7891 |
41.5375 |
46 |
50.2813 |
20.7133 |
|
22 |
35.2868 |
30.4999 |
47 |
70.9471 |
60.7199 |
|
23 |
81.3166 |
87.4367 |
48 |
42.8892 |
62.9888 |
|
24 |
0.9861 |
1.5009 |
49 |
30.4617 |
37.0477 |
|
25 |
13.8891 |
76.7950 |
50 |
18.9654 |
57.5148 |
|
51 |
19.3431 |
45.1425 |
76 |
70.2740 |
67.5645 |
|
52 |
68.2223 |
4.3895 |
77 |
54.6571 |
69.9213 |
|
53 |
30.2764 |
2.7185 |
78 |
44.4880 |
72.7509 |
|
54 |
54.1674 |
31.2685 |
79 |
69.4567 |
47.8384 |
|
55 |
15.0873 |
1.2863 |
80 |
62.1310 |
55.4842 |
|
56 |
69.7898 |
38.3967 |
81 |
79.4821 |
12.1047 |
|
57 |
37.8373 |
68.3116 |
82 |
95.6843 |
45.0754 |
|
58 |
86.0012 |
9.2842 |
83 |
52.2590 |
71.5883 |
|
59 |
85.3655 |
3.5338 |
84 |
88.0142 |
89.2842 |
|
60 |
59.3563 |
61.2395 |
85 |
17.2956 |
27.3102 |
|
61 |
49.6552 |
60.8540 |
86 |
97.9747 |
25.4769 |
|
62 |
89.9769 |
1.5760 |
87 |
27.1447 |
86.5603 |
|
63 |
82.1629 |
1.6355 |
88 |
25.2329 |
23.2350 |
|
64 |
64.4910 |
19.0075 |
89 |
87.5742 |
80.4872 |
|
65 |
81.7974 |
58.6918 |
90 |
73.7306 |
90.8398 |
|
66 |
66.0228 |
5.7581 |
91 |
13.6519 |
23.1894 |
|
67 |
34.1971 |
36.7568 |
92 |
1.1757 |
23.9313 |
|
68 |
28.9726 |
63.1451 |
93 |
89.3898 |
4.9754 |
|
69 |
34.1194 |
71.7634 |
94 |
19.9138 |
7.8384 |
|
70 |
53.4079 |
69.2669 |
95 |
29.8723 |
64.0815 |
|
71 |
72.7113 |
8.4079 |
96 |
66.1443 |
19.0887 |
|
72 |
30.9290 |
45.4355 |
97 |
28.4409 |
84.3869 |
|
73 |
83.8496 |
44.1828 |
98 |
46.9224 |
17.3900 |
|
74 |
56.8072 |
35.3250 |
99 |
6.4781 |
17.0793 |
|
75 |
37.0414 |
15.3606 |
100 |
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必须要覆盖的点的坐标 表5障碍区域4必须要覆盖的点的坐标
|
顶点序号 |
顶点的横坐标 |
顶点的纵坐标 |
顶点序号 |
顶点的横坐标 |
顶点的纵坐标 |
|
1 |
54.6982 |
70 |
1 |
90 |
75 |
|
2 |
53.7465 |
90 |
2 |
80 |
95 |
|
3 |
46.9222 |
80 |
3 |
70 |
80 |