141-flight-370

Flight 370

Challenge Description:

You have probably heard about the tragedy that happened to one of the Malaysian airplanes. Many countries support the search mission with ships, planes, and rescue services. There is also a web app which allows people to help with the search. It is called Tomnod. Thousands of volunteers are browsing the satellite images to explore the Earth and solve the real-world problems. They mark the items they have found with the special tags. You can also join the search by going to http://www.tomnod.com/ and signing in. All the search results regarding the Malaysian flight are in an XML file that you can download here. Each item found and marked on the map is represented by the following XML section:

    <Placemark id='4889783'>
        <name>Oil Slick ID 4889783</name><Snippet maxLines='0'></Snippet>
        <type>Oil Slick</type>
        <description><![CDATA[
            <img src='https://s3.amazonaws.com/explorationlab/chips/08458a6f42a780af66c05d0ef1385558.jpg' height=400 width=400><br/>
            <table width=400><tr><td width=40%>CrowdRank: <b>100%</b><br/>Confirmation: <b>2</b> people<br/>
            <td align='right' valign='bottom'>Image © DigitalGlobe 2014<br><br><a href='http://tomnod.com/nod/challenge/mh370_indian_ocean/map/983378'>See this point on <img src='http://www.tomnod.com/nod/images/logo_small.png' width=100></a>
        </tr</table>
        ]]></description>
        <styleUrl>#tag_type_130</styleUrl>
        <TimeStamp><when>2014-03-27 18:14:25.234888</when></TimeStamp>
        <Point><coordinates>79.834979564799994,6.97011026235</coordinates></Point>
    </Placemark>

An item is called a placemark. It has a name, a type, a point with coordinates, a timestamp when it was marked, and a description section with the confirmation in it.

You are given a point on the Earth surface, represented by a longitude and a latitude, and a radius in kilometers. Your task is to print out the name of the placemark that was confirmed by the largest amount of people in the given area.

Input sample:

Your program should accept a path to a filename as its first argument. The first N lines of the file contain the regions, one per line. Other lines contain the XML code itself starting with the following line:

<?xml version='1.0' encoding='UTF-8'?>

For example:

70; (96.289565663600001, 4.0044008079599998)
873; (92.749414588199997, 11.692508007600001)
98; (105.364957907, 6.6474719752600002)
20; (80.185393420699995, 7.5700396347199996)
<?xml version='1.0' encoding='UTF-8'?>
<kml xmlns='http://www.opengis.net/kml/2.2'>
<Document>

... Document body ...

</Document>
</kml>

Output sample:

For each test case print out the name of the placemark that was confirmed by the largest amount of people. If there is more than one placemark with the same maximum amount of confirmations, print out the names ordered by timestamp starting from the most recent ones, separated by comma and a single space. In case the timestamps are the same, print out placemarks ordered by Id. Print out 'None' in case there is no placemark in a given area.

For example:

Other ID 4398192, Other ID 4402502, Other ID 4437554, Other ID 4437645, Oil Slick ID 4519894
Wreckage ID 6757595
Other ID 3835555
None

Constraints:

1. R is in a range from 20 to 3000.
2. N is in a range from 10 to 15