# 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

import random

# Takes a list l of points and draws them on the picture pic
def drawPoints(l, pic):
  for point in l:
    addRectFilled(pic, point[0], point[1], 2, 2)

# Generates and returns a list of n points, each having integer 
# coordinates in the range 1 through m
def generatePoints(n, m):
  l = []
  for i in range(0, n):
    l = l + [[random.randint(1, m), random.randint(1, m)]]
  return l

# Returns true if q is strictly to the northeast of p; false
# otherwise
def isNorthEastOf(p, q):
  return ((q[0] > p[0]) and (q[1] < p[1]))

# 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):
  return ((abs(p[0] - q[0]) <= k) and (abs(p[1] - q[1]) <= k))

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

# 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):
  return ((1 <= nw[0] <= m) and (1 <= nw[1] <= m) and (1 <= se[0] <= m) and (1 <= se[1] <= m))

# Returns true if the rectangle described by its northwest and southeast
# corners is empty
def isEmpty(nw, se, l):
  # Scan all points in the list l to check if the generated
  # square is empty
  isThisAnEmptySquare = 1
  
  for r in l:
    if(isInside(r, nw, se)):
      isThisAnEmptySquare = 0

  return isThisAnEmptySquare


# Makes an m by m window and draws n randomly generated points
# (with integer coordinates) in the window.
def main(n, m, k):
  l = generatePoints(n, m)
  
  found = 0

  # case 1: Consider the square that is flush against the northwest corner
  # of the window
  nw = [1, 1]
  se = [nw[0] + k, nw[1] + k]
  if(fitsWindow(nw, se, m) and isEmpty(nw, se, l)):
    squareNW = nw
    found = 1

  # case 2: Consider squares that are flush against the left side of
  # the window and have a point touching the top side
  for p in l:
    if(p[0] <= k+1):
      nw = [1, p[0]]
      se = [nw[0] + k, nw[1] + k]
      if(fitsWindow(nw, se, m) and isEmpty(nw, se, l)):
        squareNW = nw
        found = 1
      
  # case 3: Consider squares that are flush against the top side of
  # the window and have a point touching the left side
  for p in l:
    if(p[1] <= k+1):
      nw = [p[1], 1]
      se = [nw[0] + k, nw[1] + k]
      if(fitsWindow(nw, se, m) and isEmpty(nw, se, l)):
        squareNW = nw
        found = 1


  # 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 to see if the square is empty.
  for p in l:
    for q in l:
      if((isNorthEastOf(p, q)) and isCloseEnough(p, q, k)):

        # Identify the northwest and southeast corners of the k by k 
        # square that was found
        nw = [p[0], q[1]]
        se = [nw[0] + k, nw[1] + k]

        if(fitsWindow(nw, se, m) and isEmpty(nw, se, l)):
          squareNW = nw
          found = 1

  if(found):
    pic = makeEmptyPicture(m, m)
    drawPoints(l, pic)
    addRect(pic, squareNW[0], squareNW[1], k, k)
    show(pic)
    writePictureTo(pic, "points.jpg")