Programming Challenge from Kattis: Watchdog I've tried to solve the kattis-challenge called Watchdog. My code works just fine, but it was 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 was also slower. And it's the speed that I'm having issues with.

Example input:

3
10 2
6 6
5 4
20 2
1 1
19 19
10 3
1 1
1 2
1 3


Example output:

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&gt;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 &lt; 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&lt;=side and x-dist&gt;=0:
                if y+dist&lt;=side and y-dist&gt;=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)&gt;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)&gt;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
Your solution is right, but unfortunately the time limit enforces a certain optimization. The key of this is where it says: 


  If several such point print point with lowest x, if several points with equal x, print point with lowest y


In your case, you just append all possible candidate and then you have a very complicated way to find the lowest. First of all, this complicated way could have been reduced to sorting and returning first element. 

If we think a bit further on how does itertools.product work, it will first iterate over x and then over y. This means that the first candidate we find, is the one with lowest x and lowest y of those x. This means 2 things: you don´t even need that sort, the answer will always be the first candidate. 

Now if the answer is always the first candidate, why are we keeping all candidates? And why are we still calculating other possible candidates when we already have the answer? Keeping this in mind, the solution to your time limit is simple adding a break after the possibles.append((x, y)) line. This will make us stop processing when we find the answer, and will save enough time for the time limit. 

This means all the elif len(possibles)&gt;1: part is unnecessary, making it shorter and cleaner. Another simple optimization is changing hatch_list to a set instead of a list so that the if (x, y) not in hatch_list: takes less than O(n). Its a small change that only requires changing list() to set() and append to add. 

There might be more optimization to make but the one of the break is the key to the problem and the expected optimization to make to be able to not have time limit.