題目 1990:
藍(lán)橋杯算法訓(xùn)練VIP-Collecting Luggage
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 47 解決: 31
題目描述
航班結(jié)束后，提取行李的過(guò)程并不瑣碎。手提箱和行李箱出現(xiàn)在一條傳送帶上，數(shù)百名乘客爭(zhēng)奪有利的位置從中找到并取回自己的所有物。近日，成田機(jī)場(chǎng)管理局已決定使這一過(guò)程更加高效。在重新設(shè)計(jì)行李認(rèn)領(lǐng)區(qū)前，他們需要一個(gè)模擬程序，使得乘客認(rèn)領(lǐng)行李時(shí)的耗時(shí)更平均。這個(gè)模擬假定乘客們走一條由直線段組成的路徑并使用最少的時(shí)間走到他們的行李處。
對(duì)于這個(gè)問(wèn)題，傳送帶被描述為一個(gè)簡(jiǎn)單多邊形。在傳送帶的某些點(diǎn)上出現(xiàn)一件行李，然后以恒定的速度沿著傳送帶移動(dòng)。乘客一開(kāi)始在一個(gè)傳送帶組成的多邊形外的點(diǎn)。在行李出現(xiàn)的同時(shí)，乘客以恒定的速度（大于行李移動(dòng)的速度）移動(dòng)去提取行李。乘客的路徑可以接觸但不能穿過(guò)傳送帶，且能讓乘客在最短的時(shí)間內(nèi)和行李位于同一個(gè)點(diǎn)。
在接下來(lái)這幅圖中，傳送帶被描述成多邊形ABCDEF。行李開(kāi)始在左上角（A點(diǎn)）并按時(shí)針?lè)较蜓囟噙呅芜吘壱苿?dòng)，如小箭頭所示。乘客一開(kāi)始在P點(diǎn)，并開(kāi)始按最短的時(shí)間能和行李到達(dá)同一點(diǎn)（圖中M點(diǎn)）的路徑移動(dòng)。乘客的移動(dòng)路徑如紅色箭頭所示。該圖對(duì)應(yīng)第一個(gè)輸入樣例。
對(duì)于這個(gè)問(wèn)題，傳送帶被描述為一個(gè)簡(jiǎn)單多邊形。在傳送帶的某些點(diǎn)上出現(xiàn)一件行李，然后以恒定的速度沿著傳送帶移動(dòng)。乘客一開(kāi)始在一個(gè)傳送帶組成的多邊形外的點(diǎn)。在行李出現(xiàn)的同時(shí)，乘客以恒定的速度（大于行李移動(dòng)的速度）移動(dòng)去提取行李。乘客的路徑可以接觸但不能穿過(guò)傳送帶，且能讓乘客在最短的時(shí)間內(nèi)和行李位于同一個(gè)點(diǎn)。
在接下來(lái)這幅圖中，傳送帶被描述成多邊形ABCDEF。行李開(kāi)始在左上角（A點(diǎn)）并按時(shí)針?lè)较蜓囟噙呅芜吘壱苿?dòng)，如小箭頭所示。乘客一開(kāi)始在P點(diǎn)，并開(kāi)始按最短的時(shí)間能和行李到達(dá)同一點(diǎn)（圖中M點(diǎn)）的路徑移動(dòng)。乘客的移動(dòng)路徑如紅色箭頭所示。該圖對(duì)應(yīng)第一個(gè)輸入樣例。
輸入格式
輸入包含一個(gè)或多個(gè)測(cè)試點(diǎn)來(lái)描述領(lǐng)取行李的場(chǎng)景。一個(gè)場(chǎng)景描述開(kāi)頭一行為一個(gè)單獨(dú)的整數(shù)N(3<=N<=100)，多邊形的頂點(diǎn)數(shù)。接下來(lái)N行每行兩個(gè)整數(shù)xi,yi,(|xi|,|yi|<=10000)，按逆時(shí)針順序給出多邊形頂點(diǎn)的坐標(biāo)。多邊形是簡(jiǎn)單多邊形，也就是說(shuō)它不自交，不重合。多邊形的描述后接下來(lái)一行兩個(gè)整數(shù)px,py(|px|,|py|<=10000)，乘客起始位置所在點(diǎn)的坐標(biāo)。接下來(lái)兩個(gè)正整數(shù)VL,VP(0<VL<VP<=10000)，分別是行李和乘客的速度。所有坐標(biāo)的單位是米，速度的單位是米/分鐘。
你可以假設(shè)乘客位于多邊形外。行李將會(huì)從多變形的第一個(gè)頂點(diǎn)開(kāi)始按逆時(shí)針順序沿傳送帶移動(dòng)。
輸入以一行一個(gè)單獨(dú)的0結(jié)束。
你可以假設(shè)乘客位于多邊形外。行李將會(huì)從多變形的第一個(gè)頂點(diǎn)開(kāi)始按逆時(shí)針順序沿傳送帶移動(dòng)。
輸入以一行一個(gè)單獨(dú)的0結(jié)束。
輸出格式
對(duì)于每組數(shù)據(jù)，輸出一行，包括測(cè)試數(shù)據(jù)編號(hào)（從1開(kāi)始編號(hào)）和乘客取得行李的最少時(shí)間。使用格式如樣例輸出所示（用冒號(hào)隔開(kāi)分鐘和秒），四舍五入到最近的整數(shù)。秒數(shù)占兩位（不足用前導(dǎo)0補(bǔ)齊）。
樣例輸入
6 0 40 0 0 20 0 20 20 40 20 40 40 120 40 70 100 4 0 0 10 0 10 10 0 10 100 100 10 11 0
樣例輸出
Case 1: Time = 1:02 Case 2: Time = 12:36
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情