Legrövidebb hálózat
Néhány várost üvegszálas internet kapcsolattal kötünk össze. A kábelek egyenes vonalban vezethetők két pont között. Felvehetünk csomópontokat a városokon kívül is.
Célunk a hálózat összhosszának minimalizálása.
Feladat
Írj programot, amely a városok koordinátáinak ismeretében megadja az optimális
hálózat összhosszát. Amennyiben új csomópontokat vettünk fel, ki kell írni a csomópontok koordinátáit is. Meg kell továbbá adni, hogy mely pontok vannak közvetlenül kábellel összekötve a hálózatban.
Bemenet
Az SNP.BE állomány első sora a városok N számát tartalmazza.
($2 \lt N \lt 7$). További N sorban a városok koordinátái következnek X Y sorrendben, szóközzel elválasztva. ($0 \le X$, $Y \le 100$).
Kimenet
Az SNP.KI állomány első sorába a minimális összhossz értékét írjuk
tízedestört alakban.
A következő sorba a szükséges csomópontok C száma kerüljön. Ha ez nagyobb nullánál,
akkor a következő C sor a csomópontok koordinátáit tartalmazza.
Végül az összekötésben használt szakaszokat soroljuk fel, végpontjaikkal megadva.
A városok neve: v1,v2,v3,...
A csomópontok neve c1, c2, ...
Az összekötő szakaszok megadása pl: v1 - c2
Példák
| SNP.BE | SNP.KI |
| 3
0 0
30 0
80 0 |
80.0
0
v1 - v2
v2 - v3 |
| 4
0 0
0 100
100 0
100 100 |
273.2055362658948
2
50 29
50 71
v1 - c1
v2 - c1
v3 - c2
v4 - c2
c1 - c2 |
Tesztadatok
feloldhatatlan link: snp.zip (/szakkor/bdg/0708/05ora/snp/snp.zip)
