**Introduction.**

The input is a set `P` of points in the plane (say, in a
window `W`) and a positive integer `k`.
Your task is write a program that determines if it is possible to place
a `k` × `k` square in `W` so that it is
empty (i.e., does not contain any point in `P`).

For example, here is a 500 × 500 window containing 3000 points.
If `k` were 20, your task would be to see if you can locate a
20 × 20 square somewhere in this window, so that it is empty.
Do you see the 20 × 20 empty square that was found by a program
I wrote?

**Input and Output.**

The input will come from a text file containing the set `P` of
points. You can assume that your text file looks like this:

10 52 109 399 12 70 15 402 150 100In this example, the text file contains 5 points, one point specified in each line, with the

**Searching for an empty square.**

At first glance, it might seem as though you might have to try out
infinitely many possible placements of the `k` × `k`
square and check each placement for emptiness.
However, it turns out that we can turn this into "finite" search pretty
easily.
Imagine for the moment that it is possible to place an empty
`k` × `k` square `S` in the window.
Now try to move `S` as far to the left as possible (without
violating its emptiness). Similarly, try to move `S` as far
up as possible (without violating its emptiness).
Now `S` is guaranteed to either be flush against the left side
of the window or have a point `p` in `P` flush to its
left side.
Similarly, `S` is also guaranteed to either be flush against the
top side of the window or have a point `q` in
P flush to its top side.
This means that we only have to examine
`k` × `k` squares that are:

- flush against the left side
*and*the top side of the window (there is only one such square), - flush against the left side of the window and with a point in
`P`touching the top side, - flush against the top side of the window and with a point in
`P`touching its left side, and - flush against a point
`p`in`P`on its left and a points`q`in`P`on its top.

For now, to check ifforeach pair of pointspandqinPdoifthere is ak×ksquareSthat haspflush to its left andqflush to its topthencheck ifSis empty

**How to get started.**

There are three distinct parts to your program: (i) reading input,
(ii) doing the search, and (iii) producing the output (i.e., drawing
a window, points, and square).
The search is the most important part of your program and will be worth
a large fraction of the points and so you should first focus on making as much
progress on your search as possible, leaving the input and output for later.
Specifically, if you don't want to deal with file input for now, you could just
generate a list of points at random.
Here is a simple function to do this, in case you want to use this
approach.

# 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 lAs far as output is concerned, in order to get things going, you could start off by having your program just use

**What should you do over the weekend?**

In order to help you get started on this homework over the weekend, let me
suggest a very specific task.
Write a python function:

def isEmpty(ptList, nw, se):that returns

**What to submit.**

Submit a *python* program to solve the above problem in a file called
`hw6.py`.
This file should contain a function `main()` that should get the
program going.
Your program should be well commented and easily readable.
In addition, submit a `README` file (see instructions on the
course page).