O(N*N) Solution in Python (N*N < x*y*N in avg case)


#1

import math

class Solution:

    # @param A : integer

    # @param B : integer

    # @param C : integer

    # @param D : integer

    # @param E : list of integers

    # @param F : list of integers

    # @return a strings

    def solve(self, A, B, C, D, E, F):

        graph = {i:[] for i in range©}

        vis = {i:False for i in range©}

        for i in range©:

            for j in range(i+1,C):

                dist = math.sqrt((E[i]-E[j])**2 + (F[i]-F[j])**2)

                if dist <= 2*D:

                    graph[i].append(j)

                    graph[j].append(i)

        

        up = {}

        dn = {}

        lt = {}

        rt = {}

        for i in range©:

            if F[i]+D >= B:

                up[i] = 1

            if F[i]-D <= 0:

                dn[i] = 1

            if E[i]+D >= A:

                rt[i] = 1

            if E[i]-D <= 0:

                lt[i] = 1

        

        arr = []

        for i in up:

            arr = [i]

            vis[i] = True

            for j in arr:

                if rt.get(j,0)>0:

                    return ‘NO’

                if dn.get(j,0)>0:

                    return ‘NO’         

                for k in graph[i]:

                    if not vis[k]:

                        arr.append(k)

                        vis[k]=True

        

        for i in lt:

            arr = [i]

            vis[i] = True

            for j in arr:

                if dn.get(j,0)>0:

                    return ‘NO’

                if rt.get(j,0)>0:

                    return ‘NO’                 

                for k in graph[i]:

                    if not vis[k]:

                        arr.append(k)

                        vis[k]=True

        

        return ‘YES’