COMP1721 - Higher Computing 1B

Higher Computing 1B - Week 8 Laboratory Exercises

Welcome to your fifth Computing 1B laboratory.

This lab involves:

Create a separate directory (lab08 is a good name) using mkdir for this week's lab exercises.

Exercise 1: Nearest Neighbours

Your task this week is to write a program nearest.c which reads in a set of points in 3-space and prints out the closest pair.

Your program should first ask how many points are in the set.

Your program should then read in that many points from the user.

The user will specify each point as three floating-point numbers.

When all points have been entered, your program should print the pair of points which are closest to each other and the distance between them.

If multiple pairs of points are equally close, your program may print any of the pairs.

Here is an example of how your program should behave: 

% ./nearest
How many points in your set? 5
Enter point 0: 1.7 12.44 -7.65
Enter point 1: 0.5 5.5 7.5
Enter point 2: 0.333 0.333 0.333
Enter point 3: 1.2 3.4 5.9
Enter point 4: 42.2 4.22 0.422
The closest two points are (0.5,5.5,7.5) and (1.2,3.4,5.9).
The distance between them is 2.7313.

Your program should reproduce the above behaviour exactly, except you do not have to match the format used in printing floating point numbers. It is OK as long as your program prints essentially the correct numbers.

Here are soem more examples: 

% ./nearest
How many points in your set? 2
Enter point 0: 0.0 0.0 0.0
Enter point 1: 4.0 0.0 3.0
The closest two points are (0,0,0) and (4,0,3).
The distance between them is 5.
% ./nearest
How many points in your set? 3
Enter point 0: 1.0 1.0 1.0
Enter point 1: 2.0 2.0 2.0
Enter point 2: -9999.9 1000000.3 555555555.3
The closest two points are (1,1,1) and (2,2,2).
The distance between them is 1.73205.
% ./nearest
How many points in your set? 10
Enter point 0: 1.7 2.3 1.1
Enter point 1: 9.9 2.3 4.7
Enter point 2: 3.1 0.9 9.9
Enter point 3: 1.1 1.1 1.1
Enter point 4: 5.7 8.9 3.3
Enter point 5: 6.6 3.3 1.1
Enter point 6: 0.0 0.0 0.0
Enter point 7: 9.9 9.9 9.9
Enter point 8: 1.2 3.4 5.6
Enter point 9: 7.8 9.0 1.2
The closest two points are (1.7,2.3,1.1) and (1.1,1.1,1.1).
The distance between them is 1.34164.

Implementation

There are number of restrictions on your implementation.

You must store each point in a struct dynamically allocated with malloc.

You must store pointers to these structs in array.

This array must be dynamically allocated with malloc.

You must decompose your program into separate functions for each logical tasks. Here are suggested functions: 

point *read_point(void);
void print_point(point *p);
double distance(point *a, point *b);

Hints

The distance between two points in 3-space (x1,y1,z1) and (x2,y2,z2) is:
sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2))

Finished?

Make sure you test each program thoroughly. When you are sure all are working show them to your tutor to receive this week's lab mark.

After your tutor has checked that you answers are correct and given you the lab mark, you must also submit your answers using give. Here is the command to use: 

% /home/cs1721/bin/classrun -give lab08 nearest.c

Andrew Taylor (andrewt@cse.unsw.edu.au)
Higher Computing 1B, Computer Science & Engineering, UNSW