# 多處理機平行程式設計 作業5-2說明

## 題目:進擊的哈士奇 II

### 題目敘述

在一個遙遠的國家中正被一群哈士奇所侵擾，這群哈士奇最喜歡說的一句話就是：你守家，我去偷拆。為此苦惱不已的國王決定在他的據點中建立一座圍牆。請選擇要建圍牆的據點與其建牆的順序，這座圍牆必須滿足任兩個據點的直線路徑不會經過圍牆外，要不然就會被不能拆家而狂爆化的哈士奇所襲擊。
雖然圍牆堅不可摧，但是哈士奇很快就發現圍牆間的據點是弱點。為了預防哈士奇襲擊，據點必須派重兵防守，但是國內兵力不足，無法同時防守全部據點。還好國內開發出一個新的技術，可以透過特殊通道快速移動。此快速通道只能在據點間直線連接，二個據點間的傳送不一定需要直接連接，可以透過其他據點轉送。但是建立此通道的費用非常昂貴，費用是二個據點間的歐式距離$（\sqrt{(x_1 − x_2)^2 + (y_1 − y_2)^2} )$，請求出使所有在圍牆上的據點連通的最小成本，你可以選擇部份圍牆內的據點當中繼點來節省建置的成本。請使用 $OpenMP$ 來增加求解速度。

hint:
1. 先找凸包，凸包部分不用平行化
2. Prim's algorithm pseudocode


### 輸入輸出說明
輸入測資的部分第一行為$n$，是據點的總數，其後$n$行皆是以「據點座標$x$ 據點座標$y$」的格式。

資料範圍：
* $1 \leq n < 30$
* $-20 \leq x < 20$
* $-20 \leq y < 20$

輸出規範：
* 點與點之間的距離取至小數點後4位，其後無條件捨去
* 最終輸出也是只有小數點後四位
* 最終輸出只有一個數字，也就是成本，沒有空白、換行

舉例：
輸入檔案內：
${5}$
${0 \space 2}$
${2 \space 2}$
${2 \space 0}$
${0 \space 0}$
${1 \space 1}$

最終輸出為：
${5.6568}$

time out：35s

### 繳交格式

在Github上傳一個程式碼檔案<font color="#f00">以及對應的Makefile檔案</font>，程式碼檔名為 學號_hw5_2
例如：p12345678_hw5_2.c p12345678_hw5_2.cpp都可
Makefile就叫Makefile