e309: 充電站選址的最佳組合
Tags :
Accepted rate : 4人/4人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-07-11 20:40

Content

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

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

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

充電站等級

每天充電能力

建置成本

1級

270輛

5000萬

2級

180輛

4200萬

3級

110輛

2900萬

4級

70輛

2200萬

 

 

表三、候選充電站的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

 

 

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

需求點

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輛

Input

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

 

Output

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

 

Sample Input
0.1
Sample Output
B 1,C 1,G 1
15000,6968.15,21968.15
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (25%): 3.0s , <1K
公開 測資點#1 (25%): 3.0s , <1K
公開 測資點#2 (25%): 3.0s , <1K
公開 測資點#3 (25%): 3.0s , <1K
Hint :

官方測資,應該不會有問題吧。

Tags:
出處:
107學年度彰雲嘉區資訊學科能力競賽 [管理者:
mmi366127 (unknown)
]


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