class Kocurkovo:
    def __init__(self, meno_suboru):
        self.graf = {}
        self.krizovatka = set()
        self.hrana = {}
        with open(meno_suboru) as file:
            for line in file:
                line = line.strip().split()
                x1, y1, x2, y2 = int(line[0]), int(line[1]), int(line[2]), int(line[3])
                v1, v2 = (x1, y1), (x2, y2)

                self.krizovatka.add(v1)
                self.krizovatka.add(v2)

                if v1 not in self.graf: self.graf[v1] = {}
                if v2 not in self.graf: self.graf[v2] = {}

                self.graf[v1][v2] = set()
                self.graf[v2][v1] = set()

                vaha = round((((x1 - x2)**2) + ((y1 - y2)**2))**.5)

                self.graf[v1][v2] = vaha
                self.graf[v2][v1] = vaha

    def krizovatky(self):
        return self.krizovatka

    def ulica(self, k1, k2):
        if k1 in self.graf and k2 in self.graf[k1]:
            return self.graf[k1][k2]
        else: return None



##    def backtracking(self):
##        v1 = self.cesta[-1]
##
##        for v2 in self.graf[v1]:
##            if self.sucet > self.medzi:
##                self.sucet = self.medzi
##                self.cesta = self.prejdena
##
##                if v2 != self.ciel:
##
##                    self.prejdena.append(v2)
##
##                    self.hrany.add((v1, v2))
##                    self.hrany.add((v2, v1))
##
##                    self.backtracking()
##                    if self.sucet > self.medzi:
##                        return
##
##                    self.prejdena.pop()
##                    self.hrany.remove((v1, v2))
##                    self.hrany.remove((v2, v1))


    def trasa(self, k1, k2):
        self.cesta = []
        self.sucet = 0


        self.medzi = 0
        self.start = k1
        self.ciel = k2
        self.prejdena = []

        self.hrany = {}
##        self.backtracking()
##
        def backtracking(v1, cesta, suc):
            if v1 == k2 and suc > self.sucet:
                self.cesta = cesta
                self.sucet = suc
            elif suc > self.sucet:
                self.cesta = cesta
                self.sucet = suc

            for v2 in self.graf[v1]:
                if ((v1, v2)) not in cesta and ((v2, v1)) not in cesta:
                    backtracking(v2, [v2] + cesta, suc + self.graf[v1][v2])

        backtracking(k1, [], 0)

        return self.cesta

if __name__ == '__main__':
    k = Kocurkovo('subor1.txt')
    print('krizovatky =', k.krizovatky())
    for k1, k2 in ((120, 200), (100, 100)), ((50, 210), (50, 210)), ((190, 220), (120, 200)):
        print(f'ulica({k1}, {k2}) = {k.ulica(k1, k2)}')
    for k1, k2 in ((50, 210), (150, 50)), ((120, 200), (190, 220)), ((50, 210), (50, 210)):
        print(f'trasa({k1}, {k2}) = {k.trasa(k1, k2)}')