Next: Seating Diplomats Up: No Title Previous: Sparse Vectors

# Line Drawing

A small company is developing a brand new computer system from scratch based on some brand new, but completely backwards-incompatible technology. They know that any new computer must support graphics, and since their technology is all new, they don't have access to the standard graphics packages. So, they came to you for your expert help.

A basic part of all graphics programs is to render graphical elements onto the screen, such as lines, rectangles, and polygons. It turns out that rectangles, polygons, and even circles can be drawn by connecting several short line segments, so all that is required at this point is to draw a line segment.

Since the hardware guys don't have the high-resolution mode on the monitor working yet, we only have access to text output - and so we will test the line drawing routine you are writing with text. Create an internal array of 50x20 characters to represent the screen, and clear all the characters to '.' to represent black. Then, your job is to take two points (x1,y1) - (x2,y2), and fill in the characters in your array that connect those points with 'X'. Then, print the array when you are finished to show that your routine works.

Note that this problem is slightly harder than it first appears because lines that are mostly horizontal or vertical should appear with all the X's inbetween the points filled in without any gaps. When you are computing which points to fill in, you may use floating point numbers internally. When you go to fill in the array, you must round your floats to the nearest integer.

## Input Format

The input consists of a number of line specifications, each on a separate line. Each line has 4 numbers that represents the two points of each line segment (x1 y1 x2 y2). All X coordinates are guaranteed to be in the range [0, 49] and all Y coordinates are guaranteed to be in the range [0, 19] The list of lines is terminated by a line containing only -1.

## Output Format

The output should be the 50x20 grid that represents the line connecting the two points with 'X's on a background of '.'s

## Examples

Input 1:

```4 2 10 2
10 2 10 5
4 2 10 5
-1```

Output 1:

```..................................................
..................................................
....XXXXXXX.......................................
.....XX...X.......................................
.......XX.X.......................................
.........XX.......................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................```

Input 2:

```0 0 1 19
1 19 3 0
3 0 6 19
6 19 10 0
10 0 15 19
15 19 21 0
21 0 28 19
28 19 36 0
36 0 45 19
-1```

Output 2:

```X..X......X..........X..............X.............
X..X......X..........X..............X.............
X..X......XX........X.X............X.X............
X..X.....X.X........X.X............X.X............
X..XX....X.X........X.X...........X...X...........
X.X.X....X.X.......X...X..........X...X...........
X.X.X....X..X......X...X.........X.....X..........
X.X.X....X..X......X....X........X.....X..........
X.X.X...X...X.....X.....X........X......X.........
X.X.X...X...X.....X.....X.......X.......X.........
.XX..X..X....X....X......X......X........X........
.XX..X..X....X....X......X.....X.........X........
.XX..X.X.....X...X.......X.....X..........X.......
.XX..X.X.....X...X........X....X..........X.......
.XX..X.X......X..X........X...X............X......
.X...X.X......X.X..........X..X............X......
.X....XX......X.X..........X.X..............X.....
.X....X.......X.X..........X.X..............X.....
.X....X........X............X................X....
.X....X........X............X................X....```

Input 1 Output 1
Input 2 Output 2
Input 3 Output 3
Input 4 Output 4
Input 5 Output 5

## Our Solution

Next: Seating Diplomats Up: No Title Previous: Sparse Vectors

Chau-Wen Tseng
Mon Mar 15 13:58:05 EST 1999