#!/usr/bin/env python
# -*- coding: utf8 -*-

import sys
from math import *
from lxml import etree

rE = 6356752.314245 # earth's radius

def rotate(x, y, phi):
    return x*cos(phi) - y*sin(phi), x*sin(phi) + y*cos(phi)

def latlon_to_xyz(lat, lon):
    lat = radians(lat)
    lon = radians(lon)
    return cos(lat)*sin(lon), -cos(lat)*cos(lon), sin(lat)

def project_to_meters(lat, lon, latm, lonm):
    # azimuthal map projection centered at average track coordinate
    lon -= lonm
    xyz = latlon_to_xyz(lat, lon)
    zy = rotate(xyz[2], xyz[1], radians(90 - latm))
    lat2 = atan2(zy[0], sqrt(zy[1]**2 + xyz[0]**2))
    lon2 = atan2(xyz[0], -zy[1])

    x_meters = rE * sin(lon2) * (pi / 2.0 - lat2)
    y_meters = -rE * cos(lon2) * (pi / 2.0 - lat2)
    return x_meters, y_meters

projection = {}
def get_dist(latlon1, latlon2):
    p1, p2 = projection[latlon1], projection[latlon2]
    return sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

tree = etree.parse(sys.stdin)
gpx = tree.getroot()

if gpx.nsmap.has_key(None):
    nsmap = '{' + gpx.nsmap[None] + '}'
else:
    nsmap = ''

trk = gpx.find(nsmap + 'trk')
trksegs = trk.findall(nsmap + 'trkseg')

# prepare projection
base = None
for trkseg in trksegs:
    trkpts = trkseg.findall(nsmap + 'trkpt')
    for trkpt in trkpts:
        latlon = float(trkpt.get('lat')), float(trkpt.get('lon'))
        if base is None:
            base = latlon

        projection[latlon] = project_to_meters(latlon[0], latlon[1], base[0], base[1])

# read points into segments
clusters = []
segments = []
for trkseg in trksegs:
    trkpts = trkseg.findall(nsmap + 'trkpt')
    segment = []
    for trkpt in trkpts:
        latlon = float(trkpt.get('lat')), float(trkpt.get('lon'))
        segment.append(latlon)
    segments.append(segment)

# For each segment, consider whether it's OK to drop it.
# It _is_ OK to drop it if 80% of its points are in 5m distance from
# points from at least 3 other segments
kept_segments = []
for idx, segment in enumerate(segments):
    #print idx, len(segments)
    redundant_count = 0
    for latlon in segment:
        neighbours = 0
        for other_segment in kept_segments:
            if other_segment == segment: continue
            for other_latlon in other_segment:
                d = get_dist(latlon, other_latlon)
                if d < 5: # closer than 5m
                    neighbours += 1
                    break
                if d > 2000:
                    # This is likely too far away
                    break
            if neighbours == 3: break # we've found enough!
        if neighbours == 3:
            redundant_count += 1
    if redundant_count > len(segment) * 0.8:
        # 80% of points are redundant, remove!
        pass
    else:
        kept_segments.append(segment)

print "<?xml version='1.0' encoding='UTF-8'?><gpx version='1.0'><name>car gpx_d-end</name><trk>"
for segment in kept_segments:
    print "<trkseg>"
    for lat, lon in segment:
        print '<trkpt lat="%f" lon="%f"></trkpt>' % (lat, lon)
    print "</trkseg>"
print "</trk></gpx>"