1962 問題 F: 藍(lán)橋杯算法提高VIP-Asteroid Rangers
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 6 解決: 4
題目描述
這是2112年，人類已經(jīng)征服了太陽系。太空游俠隊(duì)已經(jīng)在任何大塊巖石上建立了基地（即使不適宜居住）。你作為小行星通訊部門的一員，工作是確保所有太空游俠小行星基地都能盡可能廉價(jià)地與其他小行星基地交流。你可以建立從每個(gè)基地到另外所有基地的直接交流連接，但那可能過分昂貴。相反，你想要建立最少數(shù)量的連接從而每個(gè)人都可以發(fā)送信息給其他所有人，信息可能通過一個(gè)或多個(gè)基地中轉(zhuǎn)。建立任何連接的費(fèi)用與它連接的兩個(gè)基地之間的（歐幾里德）距離成比例，所以這個(gè)問題看起來不怎么難。
但這只是一個(gè)小小的困難。小行星有一個(gè)運(yùn)動的趨勢，所以兩個(gè)當(dāng)前很接近的基地在將來不一定還是很接近。因此隨著時(shí)間流逝，你一定會樂意轉(zhuǎn)換你的交流連接，從而在任何時(shí)候你都擁有最廉價(jià)的中繼系統(tǒng)。轉(zhuǎn)換這些連接花費(fèi)時(shí)間和金錢，所以你對于了解將要執(zhí)行多少次轉(zhuǎn)換很感興趣。
一些假設(shè)讓這個(gè)任務(wù)更簡單。每個(gè)小行星可以視為一個(gè)點(diǎn)。小行星總是以固定的速度沿直線運(yùn)動。沒有小行星會和其他小行星相撞。此外，任何在時(shí)刻t(t≥0)變得最優(yōu)的中繼系統(tǒng)在任何時(shí)刻s(s滿足t<s<t+10^-6)時(shí)是獨(dú)一無二最優(yōu)的。初始最優(yōu)的中繼系統(tǒng)也是獨(dú)一無二的。
輸入
每組數(shù)據(jù)（tsinsen上的數(shù)據(jù)均為單組數(shù)據(jù)）以包含一個(gè)整數(shù)n的一行開始，其中n表示小行星基地的數(shù)量。
接下來n行，每行包含6個(gè)整數(shù)x,y,z,vx,vy,vz，前三個(gè)表示這個(gè)小行星的初始位置，后三個(gè)表示小行星在x,y,z三維上的速度（單位空間每單位時(shí)間）。
輸出
對于每組數(shù)據(jù)，輸出一行，包含數(shù)據(jù)編號和中繼系統(tǒng)需要被建立或修改的次數(shù)。
樣例輸入
3
0 0 0 0 0 0
5 0 0 0 0 0
10 1 0 -1 0 0
4
0 0 0 1 0 0
0 1 0 0 -1 0
1 1 1 3 1 1
-1 -1 2 1 -1 -1
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情