c005. 充電站選址的最佳組合 - 大魏線上解題系統

Content

某市政府將建置充電站以因應電動車的充電需求，要從10個充電站的候選點中選出若干個點來建置充電站，被選出建置之充電站其使用年限可達10年。假設每個需求點的所有車輛，都是選擇離需求點最短直線距離的建置充電站進行充電。市政府考慮的總成本包含充電站建置成本、以及10年內(以每年365天來估算)市民從20個需求點至最短距離充電站的來回移動成本。本題請輸入電動車每公里的平均移動成本n (單位為元)，，再以10年為期，計算出總成本最低且充電站能力可以滿足所有需求點的充電站選址最佳組合，本題請輸出要建置哪些候選點(A~J)及其等級(1~4)、充電站建置成本、用戶移動成本、和總成本(單位為萬元，顯示到小數點以下2位數)。

充電站的規模可以分為四個等級，其每天充電能力與建置成本如表一所示。
經過調查，10年內本市20個需求點的每日充電需求輛數及其XY座標如表二所示。
市政府提供10處土地(A~J)作為充電站的候選點位址，其XY座標如表三所示。
兩個座標和的直線距離公式為，單位為公里，C/C++的次方函數可以使用pow()，開根號函數可以使用sqrt()。
每輛電動車從需求點到充電站的移動成本為直線距離每公里n元，來回為元。

表一、充電站等級與建置成本

充電站等級	每天充電能力	建置成本
1級	270輛	5000萬
2級	180輛	4200萬
3級	110輛	2900萬
4級	70輛	2200萬

表二、需求點的座標及每日充電需求輛數

需求點	X	Y	需求輛數
1	1268	453	33輛
2	1222	427	35輛
3	1345	492	22輛
4	1151	429	29輛
5	1265	527	28輛
6	1207	589	34輛
7	1167	630	37輛
8	1166	582	45輛
9	1142	528	37輛
10	1045	503	45輛
11	1087	597	50輛
12	948	605	33輛
13	831	426	29輛
14	816	350	35輛
15	927	382	43輛
16	823	493	42輛
17	816	584	23輛
18	689	444	34輛
19	760	241	31輛
20	678	271	37輛

表三、候選充電站的XY座標位置

候選點	X	Y
A	1184	463
B	1262	593
C	1158	418
D	957	562
E	872	343
F	725	302
G	674	448
H	864	377
I	605	315
J	920	427

Input

一個浮點數n，。n為電動車每公里的平均移動成本(單位為元)。

Output

輸出兩列字串，第一列字串為充電站選址最佳組合，每個建置之充電站需輸出候選點(A~J的字元)及其等級(1~4的整數)，以空格隔開。不同充電站則以逗號隔開，並依照A→J之順序列出。第二列字串為此充電站選址組合的成本，依序包括充電站建置成本(整數，單位為萬元)、用戶移動成本(浮點數，單位為萬元，顯示到小數點以下2位數)、和總成本(浮點數，單位為萬元，四捨五入顯示到小數點以下2位數)，以逗號隔開。

Sample Input #1

範例1輸入：
0.1

範例2輸入：
0.4

範例3輸入：
0.8

Sample Output #1

範例1輸出 ：
B 1,C 1,G 1
15000,6968.15,21968.15

範例2輸出 ：
A 2,B 2,D 2,F 3,H 2
19700,17690.31,37390.31

範例3輸出 ：
A 2,B 2,D 2,F 4,G 4,H 2
21200,32780.13,53980.13

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (25%): 1.0s , <1K
公開測資點#1 (25%): 1.0s , <1K
公開測資點#2 (25%): 1.0s , <1K
公開測資點#3 (25%): 1.0s , <1K

Hint ：

Tags:

出處:

107雲嘉南考古題 [管理者： coolsea(coolsea) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」