TA的每日心情 | 開心 2015-6-17 11:50 |
---|
簽到天數: 177 天 [LV.7]常住居民III
金牌會員
- 積分
- 1437
|
發表於 2015-4-19 21:56:10
|
顯示全部樓層
###Google Code Jam Round 1A-C Translate
Problem C-Logging
Small-18pts. Large-34pts. Sigma-52pts.
森林之中有N顆樹,每棵樹上有一隻松鼠。
定義森林的boundry是一個凸多邊形,包含裡面所有的樹。
(就是凸包啦XD)
每顆樹都是一個在2D座標平面上的點(Xi,Yi),而森林的booundry就是森林的凸包。
有些樹在森林的boundry上,就代表它們在凸包的邊或角上。
松鼠們好奇的是他們的樹距離boundry有多遠?
每次會有一隻松鼠跳下來,查看有多少樹需要被砍才能讓他的樹位於森林的新boundry上。
他們會一個一個按照編號把這個數目記錄到(萬年神木)木頭上。
你的任務就是(看看)計算木頭上面寫著什麼。
Input
測資筆數T
[
有多少樹N
[
樹X座標 樹Y座標
]*N
]*T
Output
Case #(第幾筆):
[
第i顆數最少需要砍倒幾顆樹才能到凸包上
]*N(N棵樹)
Small dataset(18 pts.)
1 <= T <= 100
1 <= N <= 15
Large dataset(34 pts.)
1 <= T <= 14
1 <= N <= 3000
Sample Input
[省略]
Sample Output
[省略]
Conclusion
簡而言之
給定N個點,對每一個點計算要刪掉幾個點才能移動它到凸包的邊點上。
用GCJ格式輸出。
本翻譯完全沒有經過Google Translate.(XD
順便求pC-Large神解啊: )
|
|