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.
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
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)