200804网友练习《自来水管连接模型》

各个击破

自来水管道连接问题

自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。

表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

zhuangqg6855

不懂！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

为你奋斗

1.先把4个障碍区用约束条件表示出来（可以先手工试一下）
2.然后写一个循环验证100个用户是否满足全部的障碍区