---
# System prepended metadata

title: 多處理機平行程式設計 作業1-2說明

---

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


## 題目:進擊的哈士奇


### 題目敘述

在一個遙遠的國家中正被一群哈士奇所侵擾，這群哈士奇最喜歡說的一句話就是：你守家，我去偷拆。為此苦惱不已的國王決定在他的據點中建立一座圍牆。請選擇要建圍牆的據點與其建牆的順序，這座圍牆必須滿足任兩個據點的直線路徑不會經過圍牆外，要不然就會被不能拆家而狂爆化的哈士奇所襲擊。假設建牆的順序是 $p_1$ $\to$ $p_2$ $\to$ $p_3$ $\to$ $p_4$ $\to$ $p_1$ ，則只需要輸出 $p_1$ $p_2$ $p_3$ $p_4$（編號間用空格區隔），其中圍牆的起始點是這些據點中最左邊的據點，若有二個據點有相同的 $x$，則以最小的 $y$ 為起始點。請使用 MPI 來增加求解速度。


### 輸入輸出說明

第一行只有一個數字 $n$，代表共 $n$ 個據點，其中$100$ $\leq$ $n$ $\leq$ $12000$。。接下來 $n$ 行中，每行有二個數字，數字間用空格隔開，代表據點的座標。據點的編號從 $1$ 開始，第 $i$ 筆座標代表第 $i$ 的據點的位置，其中$1$ $\leq$ $i$ $\leq$ $n$。
例如：
$\quad 5$
$\quad 0 \space 0$
$\quad 0 \space 2$
$\quad 2 \space 2$
$\quad 2 \space 0$
$\quad 1 \space 1$
其解答為 
$\quad$$1$ $2$ $3$ $4$



### 繳交格式

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