# Programmer: Sriram Pemmaraju
# Date: 2-24-2009
# This is a solution to HW 6. It searches a window filled with points
# for an empty k by k square

# Returns true if q is strictly to the northeast of p; false
# otherwise
def isNorthEastOf(p, q):

# Returns true if the x-coordinates of p and q and the y-coordinates of
# p and q are within k units of each other
def isCloseEnough(p, q, k):

# Returns true if r is strictly inside the rectangle with northwest
# corner nw and southeast corner se.
def isInside(r, nw, se):

# Returns true if the rectangle with northwest corner nw an southeast corner
# se fits in an m by m window
def fitsWindow(nw, se, m):

# Returns true if the rectangle described by its northwest and southeast
# corners is empty. I described this in class.
def isEmpty(nw, se, l):

#The main function. It first reads a set of points from a file, then
#prompts the user for k, and then searches the window W for an empty
#k by k square.
def main():

  #Boolean that keeps track of whether an empty k by k square has
  #been found or not. Initially, this has not been found and so found
  #is false
  found = False
  
  #Code for input should go here. If you don't want to deal with
  #input initially, just generate points at random, as described in
  #the handout and prompt the user for k
  # MISSING CODE should go here

  # case 1: Consider the square that is flush against the northwest corner
  # of the window. There are no loops in this code, since only one
  # specific case is being considered.
  # MISSING CODE should go here
  # If you find an empty square, set found to True and also keep track
  # of the northwest corner of the square that was found.

  # case 2: Consider squares that are flush against the left side of
  # the window and have a point touching the top side. You will need a 
  # single for loop for this code.
  # MISSING CODE should go here
  # If you find an empty square, set found to True and also keep track
  # of the northwest corner of the square that was found.

      
  # case 3: Consider squares that are flush against the top side of
  # the window and have a point touching the left side. You will need a
  # single for loop for this code.
  # MISSING CODE should go here
  # If you find an empty square, set found to True and also keep track
  # of the northwest corner of the square that was found.


  # Case 4: Generates pairs of points p and q, checks if q is to the
  # northeast of p, checks if p and q are close enough to be flush against
  # a k by k square, and if so generates the northwest and southeast corners
  # of the k by k square. Then scans all points in the list l to see if the 
  # generated square is empty. You will need two nested for-loops for this
  # code.
  # I have provided the nested for-loops
  for p in ptList:
    for q in ptList:
      # MISSING CODE should go here. This checks if there is a k × k square S that has p 
      # flush to its left and q flush to its top and if S is empty
      # If you find an empty square, set found to True and also keep track
      # of the northwest corner of the square that was found.

  
  # Code for output should go here. Draw a window with all the points. If your program is 
  # able to find an empty k × k square, found will be true and in this case it should display 
  # the square as well in the window; otherwise it should only display a text message, something 
  # like "Empty Square Not Found."