Letöltés: gyalogtura.java import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.util.Queue; import java.util.LinkedList; import static java.lang.Math.sin; import static java.lang.Math.cos; import static java.lang.Math.sqrt; import static java.lang.Math.atan2; class Node{ Node next; int id; public Node(int myid){ next = null; id = myid; } } class Telepules{ double sz,h; String nev; Node first; //beszúrás az éllista elejére public void insert(int id){ Node hely = new Node(id); hely.next = this.first; this.first = hely; } public Telepules(double sz, double h, String n){ this.sz = sz; this.h = h; this.nev = new String(n); first = null; } } class Terkep { Telepules helyek[]; int N; // gömbi távolság meghatározása // Vincenty-formula // http://en.wikipedia.org/wiki/Great-circle_distance public double tav(int a, int b){ double R = 6371; // a Föld sugara double s1 = Math.toRadians(helyek[a].sz); double s2 = Math.toRadians(helyek[b].sz); double h1 = Math.toRadians(helyek[a].h); double h2 = Math.toRadians(helyek[b].h); double dh = h1-h2; double x = sqrt((cos(s2)*sin(dh))*(cos(s2)*sin(dh))+ (cos(s1)*sin(s2)-sin(s1)*cos(s2)*cos(dh))*(cos(s1)*sin(s2)-sin(s1)*cos(s2)*cos(dh))); double y = sin(s1)*sin(s2)+cos(s1)*cos(s2)*cos(dh); double fi = atan2(x, y); return R*fi; } public Terkep(String fnev, int N) throws IOException{ // beolvasás this.N = N; helyek = new Telepules[N]; BufferedReader BE = new BufferedReader(new FileReader(fnev)); for(int i = 0; i<N; i++){ String sor = BE.readLine(); String nev = sor.split(" ")[0]; double sz = Double.parseDouble(sor.split(" ")[1]); double h = Double.parseDouble(sor.split(" ")[2]); helyek[i] = new Telepules(sz,h,nev); } BE.close(); // éllisták meghatározása for(int i = 0; i<N-1;i++) for(int j = i+1; j < N; j++){ if(tav(i,j)<=20.0){ helyek[i].insert(j); helyek[j].insert(i); //System.out.println(helyek[i].nev+" "+helyek[j].nev+ " "+tav(i,j)); } } } public int keres(String hely){ int E = 0, U = N-1, K = (E+U)/2; while(E<=U && hely.compareTo(helyek[K].nev)!=0){ if(hely.compareTo(helyek[K].nev) < 0) U = K - 1; else E = K + 1; K = (E+U)/2; } if(E<=U) return K; else return -1; } public void szomszed(int i){ System.out.println(helyek[i].nev+" szomszédai: "); Node n = helyek[i].first; while(n != null){ System.out.print(helyek[n.id].nev+" "); n = n.next; } } } class Bejaro{ int d[]; int apa[]; boolean volt[]; Queue<Integer> Sor; Terkep T; public void kiir(int hely){ if(apa[hely]!=hely) kiir(apa[hely]); System.out.print(" "+T.helyek[hely].nev); } public void szelessegi(int START, int CEL){ //előkészületek //System.out.println(T.helyek[START].nev+" -> "+T.helyek[CEL].nev); Sor = new LinkedList<Integer>(); d = new int[T.N]; apa = new int[T.N]; volt = new boolean[T.N]; for(int i = 0; i<T.N; i++){ volt[i] = false; } d[START] = 0; apa[START] = START; volt[START] = true;; Sor.add(START); //bejárás while(!Sor.isEmpty() && !volt[CEL]){ int x = Sor.remove(); Node n = T.helyek[x].first; while(n != null){ if(!volt[n.id]){ d[n.id] = d[x] + 1; apa[n.id] = x; volt[n.id] = true; Sor.add(n.id); } n = n.next; } } //kiírás if(!volt[CEL]){ System.out.println("0"); System.out.println("LEHETETLEN"); } else { System.out.print(d[CEL]); kiir(CEL); System.out.println(); } } public Bejaro(Terkep mo, String fnev) throws IOException{ T = mo; BufferedReader BE = new BufferedReader(new FileReader(fnev)); int db = Integer.parseInt(BE.readLine()); for(int i = 0; i < db; i++){ String sor = BE.readLine(); int START = T.keres(sor.split(" ")[0]); int CEL = T.keres(sor.split(" ")[1]); szelessegi(START, CEL); } } } class gyalogtura { public static void main(String args[]) throws IOException{ Terkep T = new Terkep("magyarorszag.csv",3137); Bejaro B = new Bejaro(T,"tura.be"); } } |