Food Truck IEEEXtreme 10.0

As cited in the description this problem was proposed by Nokia so I thought it will be hard however it was one of the easiest problems in the IEEEXtreme 10.

The problem consist of finding subscribers in radius `r` of a given GPS coordinate.

The information about the subscribers are given in the form

```Date&Time,Latitude,Longitude,PhoneNumber
10/21/2016 13:34,18.912875,72.822318,9020320100
10/21/2016 10:35,18.9582233,72.8275845,9020320024
10/21/2016 15:20,18.95169982,72.83525604,9020320047
......
```

First we need to read the data then parse the date&time. For that I used datetime library in python and with little help from strftime the job is done

```In : from datetime import datetime

In : datetime.strptime("10/21/2016 13:34", "%m/%d/%Y %H:%M")
Out: datetime.datetime(2016, 10, 21, 13, 34)

```

Then I used Haversine formula to calculate the distance between two GPS points.

```from math import radians, cos, sin, asin, sqrt

def haversine(lon1, lat1, lon2, lat2):
"""
Calculate the great circle distance between two points
on the earth (specified in decimal degrees)
"""
# convert decimal degrees to radians
lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])

# haversine formula
dlon = lon2 - lon1
dlat = lat2 - lat1
a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
c = 2 * asin(sqrt(a))
r = 6378.137
return c * r

```

Then I created a empty dictionary with the subscriber's phone as the key and for the value [date, distance] . Then read line by line if the line I found is a newer position of the subscriber replace the date and distance.

```d = {}
for line in sys.stdin:
subscriber  = line.strip().split(",")

dat = datetime.strptime(subscriber, "%m/%d/%Y %H:%M")
h = haversine(lon, lat, float(subscriber), float(subscriber))
if item in d:
if dat > d[subscriber]:
d[subscriber] = [dat, h]
else:
d[item] = [dat, h]

```

Finally all I need to do is to check if the distance is less than the given radius. then just print the sorted phone numbers .

```res = []
for phone in d:
if  d[phone]<=r:
res.append(phone)

print ",".join([phone for phone in sorted(res)])
```

The complete code:

```from datetime import datetime
from math import radians, cos, sin, asin, sqrt
import sys

def haversine(lon1, lat1, lon2, lat2):
"""
Calculate the great circle distance between two points
on the earth (specified in decimal degrees)
"""
# convert decimal degrees to radians
lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])

# haversine formula
dlon = lon2 - lon1
dlat = lat2 - lat1
a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
c = 2 * asin(sqrt(a))
r = 6378.137
return c * r

lat, lon = map(float, raw_input().split(","))
r = float(raw_input())
raw_input()
d = {}
for line in sys.stdin:
subscriber  = line.strip().split(",")

dat = datetime.strptime(subscriber, "%m/%d/%Y %H:%M")
h = haversine(lon, lat, float(subscriber), float(subscriber))
if subscriber in d:
if dat > d[subscriber]:
d[subscriber] = [dat, h]
else:
d[subscriber] = [dat, h]
res = []
for phone in d:
if  d[phone]<=r:
res.append(phone)

print ",".join([phone for phone in sorted(res)])
```