{"kind":"task","effective_mode":"full","benchmark":{"kind":"benchmark","effective_mode":"full","slug":"hlce","formal_name":"Humanity's Last Code Exam","introduction":"Humanity's Last Code Exam evaluates problem solving and code generation using ICPC World Finals and IOI problems. The project describes 235 problems; this import selects its public ICPC dataset of 146 problems.","introduction_ja":"","introduction_en":"","category":"Category not supplied","task_count":null,"acquisition_status":"Acquisition status not supplied","official_url":"https://humanity-s-last-code-exam.github.io/website/","indexing_mode":"noindex","profile":{"resources":[],"task_format":"","scoring":"","metric":"","size":"","answer_access":"","license":"","citation":"","maintainer":"","released":"","why_hard":"","related":[]}},"task_id":"57418f8c-e7a9-5ce7-bac6-d8f9f67b1e30","task_key":"ICPC~2dWorld~2dFinals--examples--2012~5fJ","task_revision_id":"2","upstream_id":"2012_J","short_description":"Shortest Flight Path","config":"ICPC-World-Finals","split":"examples","body":"{\"platform\":\"atcoder\",\"question_content\":\"## Problem Statement\\n\\nCommercial flights are statistically quite safe (in terms of number of deaths per passenger-kilometer, only going to the moon is safer). But there are still reasons for precautions and safety regulations. An early such rule was the so-called “60-minute rule,” which required that a two-engine plane must always be within 60 minutes of the nearest adequate airport along its entire flight path. A variety of similar rules have existed, but at their core, they remain the same: the flight path cannot take the airplane more than a certain maximum allowed distance from the nearest airport. With these restrictions, planes cannot always use a direct route for flying from one airport to another.\\n\\nIn this problem, we will compute the shortest flight path between two airports while adhering to a maximum allowed distance rule. A plane going from airport 2 to airport 3 has to detour from the direct route via the region around airport 1. Note that the plane would not necessarily have to go to airport 1 itself.\\n\\nThings are further complicated by the fact that planes have limited fuel supply, and to go longer distances they may need to make a stopover at intermediate airports. Thus, depending on the fuel capacity, a plane going from airport 2 to airport 3 might have to stop over at airport 1 (or the fuel capacity might be too low even to go to airport 1, in which case the trip would be impossible to make).\\n\\nWe make the following simplifying assumptions:\\n\\n1. The surface of the earth is a sphere of radius 6370 km.\\n2. Both time and fuel consumption are directly proportional to distance traveled. In other words, we are interested only in total distance traveled.\\n3. The difference in distance caused by planes flying at different altitudes is negligible. Thus, effectively, we assume them to be flying along the earth’s surface.\\n4. A plane may stop for refueling at as many intermediate airports as needed, each time getting a full tank.\\n\\n## Input\\n\\nThe first line of each test case contains two integers \\\\(N\\\\) and \\\\(R\\\\), where \\\\(2 \\\\leq N \\\\leq 25\\\\) is the number of airports and \\\\(1 \\\\leq R \\\\leq 10,000\\\\) is the maximum allowed flight distance (in km) from the nearest airport.\\n\\nEach of the next \\\\(N\\\\) lines contains two integers \\\\(\\\\phi\\\\) and \\\\(\\\\theta\\\\) satisfying \\\\(0 \\\\leq \\\\phi < 360\\\\) and \\\\(-90 \\\\leq \\\\theta \\\\leq 90\\\\), the longitude and latitude (respectively) of an airport, in degrees. The airports are numbered according to their order in the input starting from one. No two airports are at the same position.\\n\\nFollowing this is a line containing an integer \\\\(Q\\\\), satisfying \\\\(1 \\\\leq Q \\\\leq 100\\\\). Each of the next \\\\(Q\\\\) lines contains three integers \\\\(s\\\\), \\\\(t\\\\), \\\\(c\\\\) satisfying \\\\(1 \\\\leq s, t \\\\leq N\\\\), \\\\(s \\\\neq t\\\\), and \\\\(1 \\\\leq c \\\\leq 50,000\\\\), indicating a plane going from airport \\\\(s\\\\) to airport \\\\(t\\\\) with a fuel capacity yielding a range of \\\\(c\\\\) km.\\n\\n## Output\\n\\nFor each test case, display the case number followed by one line for each query containing the length in km of the shortest flight path between airport \\\\(s\\\\) and \\\\(t\\\\), subject to the fuel constraint \\\\(c\\\\). Display the length accurate to three decimal places. If there is no permissible path between the two airports, then display the word `impossible` instead.\\n\\nYou may assume the answer is numerically stable for perturbations of up to 0.1 km of \\\\(R\\\\) or \\\\(c\\\\).\\n\\n## Sample Input\\n\\n```\\n3 2000\\n0 0\\n0 30\\n30 0\\n3\\n2 3 5000\\n2 3 4000\\n2 3 3000\\n```\\n\\n```\\n2 10000\\n45 45\\n225 -45\\n2\\n1 2 50000\\n2 1 50000\\n```\\n\\n## Sample Output\\n\\n```\\nCase 1:\\n4724.686\\n6670.648\\nimpossible\\nCase 2:\\nimpossible\\nimpossible\\n```\",\"question_title\":\"Shortest Flight Path\"}","display_format":"text","language":"","answer_status":"published","assets":[],"source_url":"https://humanity-s-last-code-exam.github.io/website/","history":"initial import","indexing_mode":"noindex","subproblems":[],"grids":[]}