Všeobecné pokyny
Úlohu riešte v jazyku Pascal (dialekt Turbo Pascal v.7.0 alebo
kompatibilný) alebo C (dialekt Turbo C++ v. 3.0 alebo kompatibilný).
Zdrojový text v šho riešenia uložte do súboru \verb"OBLOHA.PAS" resp.
\verb"OBLOHA.CPP" (celé riešenie musí byť uložené v tomto súbore).
Môžete
použiť štandardné knižnice uvedených dialektov.
V š program bude čítať vstupné údaje z textového súboru \verb"OBLOHA.IN"
a
vypisovať riešenia na~obrazovku počítača vo~form te presne stanovenom
zadaním úlohy. Môžete predpokladať, že vstupné údaje zodpovedajú popisu
v~zadaní. Riešenie píšte bielou farbou na obrazovku v~štandardnom textovom
móde, pred začatím vlastnej činnosti programu nezabudnite zmazať obrazovku,
nevypisujte na obrazovku žiadne iné inform cie okrem tých, ktoré sú
požadované zadaním.
Nemusíte riešiť všetky podúlohy zadania, každ časť je bodovan
samostatne. Programy, ktoré nemožno skompilovať alebo spustiť, nebudú
hodnotené.
Zadanie úlohy
V jednej nemenovanej krajine je v~lesíku pod horami ukryté Stredisko
pre
Kozmický Prieskum. V~tomto stredisku majú mnoho teleskopov, ktorými
vedci
neust le skúmajú hviezdnu oblohu. Vašou úlohou bude napísať program,
ktorý im
uľahčí pr cu na~mnohých projektoch.
Hviedzna obloha je reprezentovan mriežkou o~rozmeroch $X_0 \times
Y_0$. Na
oblohe teleskopmi rozoznali $N$~hviezd, pričom každ bola na~celočíselných
súradniciach $X_i, Y_i,$ kde $0 \le X_i < X_0$ a $0 \le Y_i <
Y_0$.
O~každej hviezde ešte vieme, aký m jas, čiže ako silno svieti.
Tento jas
označíme ako celé číslo $Z_i$, pričom $-100 \le Z_i \le 100$.
Vo vstupnom súbore sú na prvom riadku čísla $X_0$ a $Y_0$. Na druhom
riadku sa
nach dza počet hviezd $N$ a na nasledujúcich $N$ riadkoch sú tri čísla
popisujúce každú hviezdu, $X_i\ Y_i\ Z_i$. Na ďalších riadkoch nasledujú
údaje špecifické pre podúlohy (b) a (f) ktorých popis je uvedený ďalej.
Vedci rozdeľujú hviezdy do niekoľkých kategórií podľa ich intenzity.
Tieto
kategórie sú nasledovné:
A 100 až 90
D 49 až 10
B 89 až 70
E 9 až -19
C 69 až 50
Fx -20 až -100
Môžete predpokladať, že teleskopy nemajú vysokú rozlišovaciu schopnosť.
Teda rozmery oblohy sú nanajvýš $\rozmer \times \rozmer$ a~počet hviezd
na oblohe je v rozmedzí $1 < N \le \hviezd$. Taktiež neexistujú
dve hviezdy
s~rovnakými súradnicami.
a. Do prvých šiestich riadkov vypíšte na pozíciu 2 n zov príslušnej
kategórie a na~pozíciu 5 koľko hviezd tejto kategórie je na~oblohe.
b. Vo vstupnom súbore sa na ďalšom riadku po~popise hviezd nach dzajú
súradnice dvoch bodov $A_X, A_Y, B_X, B_Y$. Tieto body tvoria dva
protiľahlé rohy obdĺžnika na~oblohe.
Do~riadku 8 od pozície 2 vypíšte počet hviezd s~{\bf kladnou} intenzitou
ktoré
sa nach dzajú v~tomto obdĺžniku. Hviezda nach dzajúca sa na okraji
obdĺžnika
doň patrí.
c. Dve hviezdy, ktoré sú z~celej oblohy k~sebe najbližšie tvoria útvar
nazývaný dvojhviezda. Intenzita dvojhviezdy je rovn súčtu intenzít
jej dvoch
hviezd. Vašou úlohou je n jsť {\bf najjasnejšiu} dvojhviezdu, pričom
ak je takých
viac, môžete n jsť ľubovoľnú. Do riadku 24 od pozície 2 vypíšte text
"{\tt Dvojhviezda ma priemer D a intenzitu Z.}",
kde Z je intenzita najjasnejšej dvojhviezdy a~D je vzdialenosť jej
hviezd.
Vzdialenosť vypíšte vždy s presnosťou na dve desatinné miesta.
d. Keď sa voľným okom pozriete na oblohu, dve blízke hviezdy sa v m
javia ako jedna. Pre naše účely tvrdíme, že jasnejšia hviezda zakrýva
slabšiu,
ak je ich štvorec vzdialenosti (vzdialenosť na druhú) menší ako rozdiel
ich
intenzít. Na riadok 10 od pozície 2 vypíšte text "{\tt Voľným okom
vidno Q
hviezd.}", kde Q je počet hviezd, ktoré nie sú zakryté žiadnou inou.
e. Jeden výskumný projekt sa týka revidovania stredovekých
astronomickým pozorovaní. Je potrebné zistiť, koľko je vlastne na oblohe
súhvezdí. Súhvezdie je zoskupenie hviezd, pričom každ hviezda
patrí do pr ve
jedného súhvezdia. Súhvezdie môže byť aj jedin hviezda. Ak je
vzdialenosť
dvoch hviezd {\bf menšia alebo rovn sedem}, tak musia patriť
do jedného
súhvezdia.
Opačne to platiť nemusí. Do riadku 12 od pozície 2 vypíšte text "{\tt
Súhvezdí je W.}", kde W je najväčší možný počet súhvezdí na oblohe.
f. Jedna nemenovan počítačov firma si chce ako reklamu na
oblohu
umiestniť svoj satelit so štvorcovým firemným logom. Chcú aby toto
logo bolo
čo najväčšie, ale nesmie prekrývať žiadnu z~hviezd. Aby sa dalo ľahko
čítať
zo zeme, musí byť otočené tak, aby jeho hrany boli rovnobežné so súradnicovými
osami. Súradnice vrcholov štvorca sú celočíselné a logo nesmie
prečnievať z oblohy.
Ak hviezda leží na okraji loga, je ním prekryt . N jdite čo najväčší
štvorec na oblohe, ktorý nepokrýva žiadnu hviezdu. Ak je takých viac,
vyberte
taký, ktorého prv súradnica je čo najmenšia a ak je aj takých
viac tak taký,
ktorého druh súradnica je čo najmenšia. Do riadku 14 od pozície
2 vypíšte
text "{\tt Logo o velkosti Q na suradniciach X,Y.}", kde Q je rozmer
najväčšieho štvorca a X,Y sú súradnice jeho rohu s~najmenšími
súradnicami. Môžete predpokladať, že sa na oblohu d umiestniť
logo
veľkosti aspoň $1$.
g. In nemenovan počítačov firma, výrazne chudobnejšia,
by tiež
chcela mať na oblohe svoje logo. Nemajú však peniaze na úpravu
vzhľadu oblohy. Rozmýšľajú, ako zmeniť svoje logo tak, aby sa na oblohe
už
nach dzalo. N vrhov majú dosť, problémom je zistiť, či sa určité logo
na
oblohe už nach dza. Vo vstupnom súbore sa na ďalšom riadku nach dzajú
dve čísla $L_X, L_Y;\ (0 < L_X, L_Y \le \logo_rozmer)$
označujúce rozmery loga. Na nasledujúcich $L_Y$
riadkoch sa nach dzajú reťazce skladajúce sa z~bodiek a hviedzičiek
o~dĺžke $L_X$. Hviezdičky reprezentujú hviezdy a bodky pr zdnu oblohu.
Bod na spodnom ľavom rohu m súradnice $0,0$.
Je samozrejmé, že každé logo obsahuje aspoň jednu hviezdu.
Vašou úlohou je zistiť, či sa dané logo nach dza na oblohe. Do riadku
16
od pozície 2 vypíšte text "{\tt Logo sa na oblohe nenachadza.}" ak
logo
na oblohe nie je, alebo text "{\tt Logo sa nachadza na suradniciach
X,Y.}" , kde X, Y sú súradnice rohu loga. Vypíšte roh s~najmenšími
súradnicami.
Ak sa dané logo na oblohe nach dza viackr t, vyberte to,
ktorého prv súradnica je čo najmenšia a ak je aj takých viac
tak to,
ktorého druh súradnica je čo najmenšia. Logo sa nemôže ot čať
a nesmie
prečnievať z oblohy.
h. Nadn rodn kozmick agentúra pl nuje vyslať vesmírnu sondu
Deep Space 2 na prieskum vesmíru. Úlohou tejto sondy je preskúmať čo
najviac hviezd. Sonda bude mať veľmi m lo pohonných l tok a preto nebude
vedieť meniť svoj kurz. Vašou úlohou je navrhnúť dr hu v~tvare priamky,
ktor bude prech dzať čo najviac hviezdami. Do riadku 18 od pozície
2
vypíšte text "{\tt Deep Space 2 preskuma nanajvys Q hviezd.}", kde
Q je
najvyšší počet hviezd, ktoré ležia na priamke.
Príklad vstupu: \hskip 5.5cm Hviezdna obloha:
21 31
30__ . . . . . . . . . . . . . . . . . . . . .
29
. . . .-1 . . . . . . . . . . .10 . . . .
3 4 8
. . 0 . . .10 . . . . . . . . . . . . . .
1 10 12
. . . . . . . . . . . . . . . . . . . . .
5 12 6
. 9 . 6 . 6 .14 . . . . . . . . . . . . .
7 8 7
25__ . . . . . . . . . . . . . . . . . . .11 .
10 6 14
7 . . .11 . . .10 . . . . . . . . . . . .
13 6 5
. . . . . . . . . . . . . . . . . . . . .
16 9 9
6 . . . 5 . . . 2 . . . . . . . . . . . .
4 19 7
. . . . . . . . . . . . . . . 9 . . . . .
2 20 8
20__ . . 8 . . . 9 . . . . . . . . .10 . .14 .
0 22 6
. . . . 7 . . . . . . . . . . . . . . . .
0 24 7
. . . . . . . . . . . . . . . . . . . . .
1 26 9
. . . . . . . . . . . . . . . . . . . . .
3 26 6
. . . . . . . . . . . . . . . 7 . . . . .
2 28 0
15__ . . . . . . . . . . . . . . . . . . . . .
4 29 -1
. . . . . . . . . . . . . . . . . . . . .
4 24 11
. . . . . . . . . . . . . . . . . . . . .
4 22 5
. . . . . 6 . . . . . . . . . . . . . . .
5 26 6
. . . . . . . . . . . . . . . . . . . . .
6 20 9
10__ .12 . . . . . . . . . . . . . . . . . . .
6 28 10
. . . . . . . . . . . . . . . . 9 . . . .
7 26 14
. . . . . . . 7 . . . . . . . . . . . . .
8 22 2
. . . . . . . . . . . . . . . . . . . . .
8 24 10
. . . . . . . . . .14 . . 5 . . . . . . .
15 16 7
5__ . . . . . . . . . . . . . . . . . . . . .
15 21 9
. . . 8 . . . . . . . . . . . . . . . . .
16 20 10
. . . . . . . . . . . . . . . . . . . . .
16 29 10
. . . . . . . . . . . . . . . . . . . . .
19 20 14
. . . . . . . . . . . . . . . . . . . . .
19 25 11
0__ . . . . . . . . . . . . . . . . . . . . .
2 16 15 22
| |
| |
|
9 7
0 5
10 15
20
..*...*..
Tento obr zok slúži len pre n zornosť.
.........
Nikde vo vstupnom súbore sa nenach dza!
.*.*.*.*.
Čísla označujú hviezdy s danou intenzitou.
.........
Bodky označujú pr zdnu oblohu.
*...*...*
.........
*...*...*
Príklad výstupu:
(znaky "~" reprezentujú medzery; takto by mala vyzerať
obrazovka po spracovaní uvedeného vstupu):
~A~~0~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~B~~0~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~C~~0~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~D~~10~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~E~~19~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Fx~0~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Pocet~hviezd~v~obdlzniku~je~7.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Dvojhviezda~ma~priemer~1.41~a~intenzitu~19.~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Volnym~okom~vidno~24~hviezd.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Suhvezdi~je~3.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Logo~o~velkosti~9~na~suradniciach~6,9.~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Logo~sa~nachadza~na~suradniciach~0,22.~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Deep~space~2~preskuma~nanajvys~5~hviezd.~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~