Spring, 2018

Due: March 5 (midnight)

Write a program to read a list of (x,y) pairs representing points in the x-y plane and print them in ascending order, according to their distance from the origin.

The first line of input is an integer n (1 <= n <= 1000)
representing the number of points in the list. n is followed
by 2n additional lines of input containing the coordinates of the
points to be sorted. For example, the list { (3,4), (4,2),
(0,-5), (1,3) } would be input as:

4

3

4

4

2

0

-5

1

3

You can read the values using syscall 5 (read integer).
(syscall 5 requires that only one integer appear on each line.)

The input should be stored in an array large enough to hold as
many as 1000 points. You can view the storage conceptually
as a series of pairs, as in the table below:

3 |
4 |

4 |
2 |

0 |
-5 |

1 |
3 |

You are responsible for:

1. Allocating the space for the data.

2. Deciding how to map the data to the space you allocate.

3. Determining how to address the x- and y-coordinates of
each point.

Once you have read in all the data, you need to sort it in
increasing order according to the value of (x^{2} + y^{2});
that is, the square of the distance from the point to the
origin. If two points in your list are the same distance
from the origin, they should be sorted in lexicographic order;
that is, first in increasing order according to the x-coordinate,
and if the x-coordinates are the same, then according to the
y-coordinate. If the same point appears more than once in
the input, it should appear with the same multiplicity in the
output. For example, the correct ordering of the points
(0,-5),(3,4),(4,-3),(-3,4),(-5,0),(4,-3) would be
(-5,0),(-3,4),(0,-5),(3,4),(4,-3)(4,-3).

You may use any sort method that you choose. I would
recommend using something simple like a bubble sort. Keep in
mind that when you swap two points in your list, you must swap
both their x and y coordinates.

The output of the program will consist of n lines, each containing
the x- and y-coordinates of one point in the sorted list.
For example, the output from the list of 4 points shown above
would be:

1 3

4 2

0 -5

3 4

You may assume that overflow will not occur as a result of
computing x^{2} + y^{2}.

You may use any sort method that you choose. I would recommend
using something simple like a bubble sort. Keep

in mind that when you swap two points in your list, you must swap
both their x and y coordinates.

You can run your program using the Mars IDE by entering a small
sample data set in the I/O window. You should also test your
program on a larger data set, since it is supposed to work for as
many as 1000 data points. You can use I/O redirection from a
command line prompt to run the program with input from a file with
the command:

java -jar Mars.jar lab3.asm < input.txt

I've posted a zip file containing a sample input file and the
corresponding output file. There's a link to it on the
assignment schedule web page, as well as on blackboard. I
recommend creating your own, larger, test file as well.

1. Use handin to submit a directory containing your
.asm file.