Blog

The University of Melbourne
School of Computing and Information Systems
COMP20005 Engineering Computation
Semester 2, 2020
Assignment 1
Due: 4:00pm Wednesday 30th September 2020
1 Learning Outcomes
In this assignment you will demonstrate your understanding of loops and if statements by writing a program that sequentially processes a file of input data. You are also expected to make use of functions and arrays.
2 The Story…
Contact tracing is an important measure to prevent a virus from spreading through the community. In dealing with the COVID-19 pandemic, many countries, including Australia, have taken various contact tracing measures. A core component in contact tracing is to track people’s travel trajectories, from which people who have been in close contact with a new case can be identified quickly.
In this assignment, we are given a set of trajectory data that records people’s locations at different times.
The aim is to check whether there is anyone who has violated the 5-km from home travel zone limit, and whether there have been people who are in close contact for an extended period of time.
Below is a sample list of trajectory records of a certain day (the exact date is omitted for simplicity). Each line of the list contains the information of a location visited by a user as separated by spaces (‘ ’), including:
the visited location latitude (a real number with 6 digits after the decimal point);
the visited location longitude (a real number with 6 digits after the decimal point);
the user’s home location latitude (a real number with 6 digits after the decimal point);
the user’s home location longitude (a real number with 6 digits after the decimal point);
the start time of the visit (an integer between 1 and 24 × 3600 = 86400; this is the second from the start of the day, for example, 31144 = 8 × 3600 + 39 × 60 + 4, that is, 31144 means 08:39:04);
the end time of the visit (an integer between 1 and 86400, and greater than the start time of the visit);
the user ID (a string with 8 digit or lowercase characters).
-37.817365 144.968783 -37.797329 144.965705 31144 32144 8oz05szh
-37.810009 144.962800 -37.797329 144.965705 33867 44877 8oz05szh
-37.809657 144.965221 -37.797329 144.965705 85646 85746 8oz05szh
-37.822464 144.968863 -37.810256 145.002215 41497 42511 jon362ft
-37.742099 144.964337 -37.837977 144.975683 00145 02159 kwhb16v7
-37.810019 144.962800 -37.837977 144.975683 43000 55079 kwhb16v7
-37.822464 144.968863 -37.837977 144.975683 60270 61284 kwhb16v7
-37.822464 144.968873 -37.837977 144.975683 61285 82281 kwhb16v7
-37.845590 144.971467 -37.773574 144.968853 52475 52591 wuucozwj
-37.817368 144.968786 -37.798875 144.943082 30144 65032 y4tqqn2s
For example, the first line of the list represents that User #8oz05szh visited <-37.817365, 144.968783> at time 31144 (08:39:04) and left at time 32144 (08:55:44). The user’s home is at <-37.797329, 144.965705>.
You may assume that the list will always be correctly formatted and contain at least 2 and at most 99 records.
The list is sorted by the user ID and then by the visit start time, in ascending order.
3 Your Task
Your task is to write a program that reads the list of trajectory records and outputs statistics calculated on it. The assignment consists of the following four stages (Stage 4 is for a challenge and is optional).
3.1 Stage 1 – Processing the First Record (Marks up to 5/10)
Write a program that reads the first line of the input data, and prints out for the first record: the user ID, the latitude and the longitude of the visited location, the start and end times of the visit, and the distance (in kilometres, 2 digits before and after decimal point) from the home location to the visited location.
Given the coordinates of two points p1 = hlat1; long1i and p2 = hlat2; long2i, where lati and longi (i = 1; 2) represent the latitude and the longitude, the distance (in kilometres) between p1 and p2, represented by
dist(p1; p2), is calculated based on the haversine formula as follows.
dist(p1; p2) = 6371 · angle distance; where
angle distance = 2 · atan2sqrt(chord length); sqrt(1 – chord length);
chord length = sin2toRadian(lat2 – lat1)=2+
costoRadian(lat1) · costoRadian(lat2) · sin2toRadian(long2 – long1)=2
(1)
In the equation above, toRadian(x) = x · (3:14159=180) is a function that converts a latitude or longitude coordinate x to its radian value. You need to implement this function and define the constants properly in your code. Note that you should not use the constant M_PI provided by the math.h library as it is not supported by the assignment submission system under the assignment compilation settings.
The functions atan2(), sqrt(), sin(), and cos() are provided by the math.h library. If you use this library, make sure to add the -lm” flag to the gcc” command at compilation on your own machine.
The output of this stage given the above sample input should be (where mac:” is the command prompt):
mac: ./program < test0.txt Stage 1 ========== User: #8oz05szh Visited location: <-37.817365, 144.968783>
Start time: 31144
End time: 32144
Distance from home: 02.24 km
Here, 02.24 is the distance between the visited location of the first record, <-37.817365, 144.968783>, and the home location, <-37.797329, 144.965705>, as calculated using the haversine formula above.
Hint: To ensure the result accuracy, use double’s for storing the coordinates and calculating the distance value. Use %05.2f for the distance output formatting. You may also read all input data before printing out
for Stage 1.