e298: PE. Easy Triangle(⿊耀⽯柱)
Tags :
Accepted rate : 6人/6人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-07-09 01:11

Content

YCA 是⼀位Minecraft 玩家,他到了終界之後發現終界有許多的⿊曜⽯柱。
YCA 想選三柱⿊曜⽯柱,在中間鋪⼀⼤塊三⾓形的地板作為新的地標,並且根據⿊曜⽯柱圍成的三⾓形的類型來決定要⽤哪種⽅塊建造:
銳⾓三⾓形使⽤綠寶⽯磚(Block of Emerald)建造;
直⾓三⾓形使⽤鑽⽯磚(Block of Diamond)建造;
鈍⾓三⾓形使⽤⾦磚(Block of Gold)建造。

此處定義銳⾓三⾓形為三個頂點⾓⾓度皆⼩於$90$度的三⾓形;
直⾓三⾓形為其中⼀個頂點⾓⾓度等於$90$度的三⾓形;
鈍⾓三⾓形為其中⼀個頂點⾓⾓度⼤於$90$度的三⾓形。
因為這些⽅塊都⾮常的昂貴,YCA 希望使⽤的⽅塊可以越少越好,請你幫他找到三柱⿊曜⽯柱,並且使它們圍成的⾯積最⼩。

Input

第⼀⾏有⼀個正整數$t$表⽰有幾組測試資料。對於每⼀組測試資料的第⼀⾏是⼀個正整數$n$表⽰⿊曜⽯柱的數量,接下來有$n$⾏⽤空⽩隔開的兩個整數$x_i$、$z_i$表⽰⿊曜⽯柱所在的⽔平座標位置。

$t \leq 10$
$3 \leq n \leq 87$
$|x_i|, |z_i|  \leq 10^9$
保證⼀定找得到三柱不同的⿊曜⽯柱,並且能在平⾯上構成⼀個合法的三⾓形。
保證兩⿊曜⽯柱必不共點。

Output

對於每⼀組測試資料輸出⼀⾏表⽰YCA 應該要使⽤的⽅塊類型和選定的⿊曜⽯柱圍成的三⾓形⾯積。如果有很多不同類型的但都是最⼩的三⾓形,請輸出最便宜的那種(價值:⾦磚< 鑽⽯磚< 綠寶⽯磚)。因為YCA 是差不多先⽣,⽽且只要你的答案誤差在$2^{-87}$ 以內差不多都算你對ㄛ!

Sample Input
3
3
0 0
1 2
2 0
4
0 0
0 1
1 1
1 0
3
0 0
1 2
0 1
Sample Output
Block of Emerald 2
Block of Diamond 0.5
Block of Gold 0.5
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 2.0s , <1M
Hint :
Tags:
出處:
2019 NCTU PCCA Winter [管理者:
qqrainbow (愛蜜莉雅 準•學測戰士)
]


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