Next: Formatting HTML Text
Up: No Title
Previous: Finger-Friendly Domain Names
You are the chief programmer for easyBrowse Inc. -- the company that
will revolutionize the world by creating a better faster easier web
browser. Now all the new-fangled web pages keep popping up more and
more windows each time you visit their web-site: your job today is to
find the best place on the screen to place these new windows so that
they cause your customers the least pain. After talking to the
marketing people, the psychology people, the human-computer
interaction people, the advertising people, and the marketing people
again, you have come up with the following rules for placement of
windows for easy browsing (tm):
- All windows must be placed completely within the screen.
For your test window placement code, you should assume the screen is
320 240 pixels wide. Assume that in the beginning, there
are no windows on the screen. This also means that a single windows
cannot be larger than 320 240; also, windows must be at
least one pixel in both width and height.
- You want to place a window such that you occlude (overlap) the
minimum number of pixels of existing windows. For example,
suppose you have two legal choices (x, y), and (x', y)' to place
your window such that the complete window is visible on-screen.
Suppose by placing your window at (x,y), you cover up 10 pixels of
existing windows, while placing the window at (x', y'), you cover
up 42 pixels: you should place the window at (x,y). You should
minimize the total the number of pixels your placement obstructs --
you do not have to worry about the number of windows.
- If you find two points on the screen such that the occlusion
(overlap with number of pixels of other windows) is minimum, you
should break the tie by choosing the point that has the smallest y
coordinate. If the y coordinates are the same, then you should
break the tie by choosing the point with the smaller x coordinate.
This will ensure that windows are placed as close to the top (and
left) of the screen as possible. Note that this implies that the
first window you place will always be at (0, 0).
The input to your program is a list of window sizes:
10 10
320 20
319 230
319 230
120 23
-1 -1
The first number on a line is the width of the window, while the
second number is the height of the window. Note that you can be
multiple given windows of a given size and you don't a-priori know
the maximum number of windows you may have to place. A -1 -1
entry signifies end of input.
The output of your program is the placement of the windows using the
following format:
New window of size 10 x 10: Final placement: [( 0 0), ( 9 9)]
New window of size 320 x 20: Final placement: [( 0 10), (319 29)]
New window of size 319 x 230: Final placement: [( 0 10), (318 239)]
New window of size 319 x 230: Final placement: [( 1 0), (319 229)]
New window of size 120 x 23: Final placement: [(200 217), (319 239)]
Note that you are required to print the exact pixels that the top-left
and bottom-right corners of each window occupy. Further, the top-left
pixel is coordinate (0,0) and the bottom right pixel is coordinate
(319, 239).
Lets walk through what happens when we try to place the set of windows
given the previous section:
- In the beginning, there are no windows on the screen, so the
first window takes is placed at (0,0).
- The next window is a long thin window, and cannot be fit in the
top ten ``lines'' without occluding the first window. This window is
placed at (0, 10).
- The next two windows are truly massive: the first one is placed
to use up the unused space at the bottom of the screen. The next
window is the same size. It is placed at (1, 0) since this
placement allows the placement algorithm to use the unused space in
the top right part of the screen.
- The last window is placed aligned with the bottom right part of
the screen since this is now the least used part of the screen.
Test data used in judging
Next: Formatting HTML Text
Up: No Title
Previous: Finger-Friendly Domain Names
Chau-Wen Tseng
Tue Mar 14 18:48:15 EST 2000