Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Question by Ibrahim Mesecan.
Distanca maksimale
English
Traveling salesman eshte nje probleme e njohur. Sipas problemes,
shitesi duhet te udhetoje permes n ishujve, dhe pasi ti kete pershkruar te gjithe
nga nje here, te kthehet tek ishulli fillestar.
Pyetja:
Shkruani nje program qe te
marre koordinatat x dhe y te n ishujve. Me pas, programi duhet
te llogarise distancen euklidiane ndermjet cdo dy ishujve fqinje sipas rradhes se dhene
dhe te nxjerre distancen maksimale te gjetur. Ishulli i fundit eshte i lidhur me ishullin e pare.
Formati i inputit
Do t'ju jepet nje numer (n). Me pas, ne n rreshtat pasardhes
do tju jepen koordinatat x dhe y te cdo ishulli ku 1 ≤ n ≤ 40000 dhe koordinatat -5000 ≤
(x dhe y) ≤ 5000.
Formati i outputit
Nxirrni nje numer me me se shumti dy shifra mbas presjes
qe do jete distanca maksimale.
Shembull
4
1 1
2 2
2 4
1 4
|
Pergjigja
3
|
Shpjegimi:
Sipas rradhes se dhene, distancat jane:
- Ndermjet ishullit te 1-re dhe te 2-te: 1.414
- Ndermjet ishullit te 2-te dhe te 3-te: 2.0
- Ndermjet ishullit te 3-te dhe te 4-t: 1.0
- Ndermjet ishullit te 4-t dhe te 1-re: 3.0
Dhe distanca me e madhe eshte ajo ndermjet ishullit te 4-t dhe te 1-re.
Для отправки решений необходимо выполнить вход.
|