自来水管道连接问题
自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。
表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
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) | Powered by Discuz! X2.5 |