Gfrktyl

So I've tried to solve the kattis-challenge called Watchdog. My code works just fine, but it is too slow on the last test. I'm wondering if anyone sees any big algorithmic performance-issues.

A short description of the task: First line from .in states number of test-cases.
First line in each test-case gives length of a square and number of hatches respectively. For each hatch you'll have one line giving x and y-point of hatch respectively. The mission is to find a point x,y where the length from x,y to any hatch is not greater than the length from x,y to any point outside of the square. If no such point, print poodle. If several such point print point with lowest x, if several points with equal x, print point with lowest y. Hatches and these points cannot overlap.

I think one issue might be extensive usage of lists, but I'm also not sure how to avoid them. Initially I started reading one and one line from stdin, using the data. That way things looked way more readable, but it also was slower. And it's the speed that I'm having issues with.

Example in:

3

10 2

6 6

5 4

20 2

1 1

19 19

10 3

1 1

1 2

1 3

Example out:

3 6

poodle

2 2

2 2

My code:

import sys

from math import sqrt

import itertools



def findmaxdist(x1, y1, list):

'''Finds the distance from x1, y1 to the most

distant point in the list.'''

    dist = 0

    for x2, y2 in list:

        newdist = (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)

        if newdist>dist:

            dist=newdist

    return sqrt(dist)



fulltext = sys.stdin.readlines()

text = [w.rstrip('n') for w in fulltext]



cases = int(text[0])

i = 0

j = 1

while i < cases:

    side, hatches = text[j].split()

    side = int(side)

    hatches = int(hatches)

    j += 1

    hatch_list = list()

    for k in range(hatches):

        x, y = text[j].split()

        hatch_list.append((int(x), int(y)))

        j += 1



    possibles = list()

    for x,y in itertools.product(range(side), range(side)):

        if (x, y) not in hatch_list:

            dist = findmaxdist(x, y, hatch_list)

            if x+dist<=side and x-dist>=0:

                if y+dist<=side and y-dist>=0:

                    possibles.append((x, y))



    if len(possibles)==0:

        print('poodle')

    elif len(possibles)==1:

        print(str(possibles[0][0])+' '+str(possibles[0][1]))

    elif len(possibles)>1:

        smallx = min(possibles, key = lambda t: t[0])[0]

        semifinal = list((tuple for tuple in possibles if tuple[0] == smallx))

        if len(semifinal)==1:

            x,y = semifinal[0]

            print(str(x)+' '+str(y))

        elif len(semifinal)>1:

            smally = min(semifinal, key = lambda t: t[1])[1]

            final = list((tuple for tuple in semifinal if tuple[1] == smally))

            if len(final)==1:

                x,y = final[0]

                print(str(x)+' '+str(y))

        else:

            print('Error: Wrong input-format?')

    i+=1