竹園論壇

標題: Google Code Jam 2015 - Round 1A 慈善翻譯 [打印本頁]

作者: xiplus 時間: 2015-4-18 12:08
標題: Google Code Jam 2015 - Round 1A 慈善翻譯
Problem A. Mushroom Monster

[GOOGLEDOC]1kkTynqMfgR3Pu1XmL8DN4lLBG5SCx8X0RmLI60m7QBM[/GOOGLEDOC]

Problem B. Haircut
[GOOGLEDOC]189J4WSpnjRk5ubYzk_rd2z2QX3ivgVYjkexvNA7z760[/GOOGLEDOC]

Problem C. Logging
coming soon...

作者: visitorIKC 時間: 2015-4-19 21:56
###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神解啊: )

歡迎光臨竹園論壇 (http://forum.tfcis.org/)