ICPC 2012 - J. Shortest Flight Path
State the problem in your own words. Focus on the mathematical or algorithmic core rather than repeating the full statement.
Source-first archive entry
This page is built from the copied files in competitive_programming/icpc/2012/J-shortest-flight-path. Edit
competitive_programming/icpc/2012/J-shortest-flight-path/solution.tex to update the written solution and
competitive_programming/icpc/2012/J-shortest-flight-path/solution.cpp to update the implementation.
The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.
Problem Statement
Copied statement text kept beside the solution archive for direct reference.
Problem J
Shortest Flight Path
Problem ID: shortest
Commercial 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 can not 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.
In this problem we will compute the shortest flight path between two airports while adhering to a max-
imum allowed distance rule. In the figure below, which illustrates the first sample test case, any flight
route has to stay within the three circles. Thus 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.
Things 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 in the figure 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).
We make the following simplifying assumptions:
1. The surface of the earth is a sphere of radius 6370 km.
2. Both time and fuel consumption are directly proportional to distance traveled. In other words we
are interested only in total distance traveled.
3. The difference in distance caused by planes flying at different altitudes is negligible. Thus, effec-
tively, we assume them to be flying along the earth’s surface.
4. A plane may stop for refueling at as many intermediate airports as needed, each time getting a full
tank.
Input
The first line of each test case contains two integers N and R, where 2 ≤ N ≤ 25 is the number of
airports and 1 ≤ R ≤ 10 000 is the maximum allowed flight distance (in km) from the nearest airport.
Each of the next N lines contains two integers φ, θ satisfying 0 ≤ φ < 360 and −90 ≤ θ ≤ 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.
Following this is a line containing an integer Q, satisfying 1 ≤ Q ≤ 100. Each of the next Q lines
contains three integers s, t, c satisfying 1 ≤ s, t ≤ N , s 6= t, and 1 ≤ c ≤ 50 000, indicating a plane
going from airport s to airport t with a fuel capacity yielding a range of c km.
Output
For 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.
You may assume the answer is numerically stable for perturbations of up to 0.1 km of R or c.
Sample Input Output for Sample Input
3 2000 Case 1:
0 0 4724.686
0 30 6670.648
30 0 impossible
3 Case 2:
2 3 5000 impossible
2 3 4000 impossible
2 3 3000
2 10000
45 45
225 -45
2
1 2 50000
2 1 50000
Editorial
Rendered from the copied solution.tex file. The original TeX source remains
available below.
Key Observations
Write the structural observations that make the problem tractable.
State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
If the constraints matter, explain exactly which part of the solution they enable.
Algorithm
Describe the data structures and the state maintained by the algorithm.
Explain the processing order and why it is sufficient.
Mention corner cases explicitly if they affect the implementation.
Correctness Proof
We prove that the algorithm returns the correct answer.
Lemma 1.
State the first key claim.
Proof.
Provide a concise proof.
Lemma 2.
State the next claim if needed.
Proof.
Provide a concise proof.
Theorem.
The algorithm outputs the correct answer for every valid input.
Proof.
Combine the lemmas and finish the argument.
Complexity Analysis
State the running time and memory usage in terms of the input size.
Implementation Notes
Mention any non-obvious implementation detail that is easy to get wrong.
Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.
Code
Exact copied C++ implementation from solution.cpp.
#include <bits/stdc++.h>
using namespace std;
namespace {
void solve() {
// Fill in the full solution logic for the problem here.
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Source Files
Exact copied source-of-truth files. Edit solution.tex for the write-up and solution.cpp for the implementation.
\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}
\title{ICPC World Finals 2012\\J. Shortest Flight Path}
\author{}
\date{}
\begin{document}
\maketitle
\section*{Problem Summary}
State the problem in your own words. Focus on the mathematical or algorithmic core rather than repeating the full statement.
\section*{Key Observations}
\begin{itemize}[leftmargin=*]
\item Write the structural observations that make the problem tractable.
\item State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
\item If the constraints matter, explain exactly which part of the solution they enable.
\end{itemize}
\section*{Algorithm}
\begin{enumerate}[leftmargin=*]
\item Describe the data structures and the state maintained by the algorithm.
\item Explain the processing order and why it is sufficient.
\item Mention corner cases explicitly if they affect the implementation.
\end{enumerate}
\section*{Correctness Proof}
We prove that the algorithm returns the correct answer.
\paragraph{Lemma 1.}
State the first key claim.
\paragraph{Proof.}
Provide a concise proof.
\paragraph{Lemma 2.}
State the next claim if needed.
\paragraph{Proof.}
Provide a concise proof.
\paragraph{Theorem.}
The algorithm outputs the correct answer for every valid input.
\paragraph{Proof.}
Combine the lemmas and finish the argument.
\section*{Complexity Analysis}
State the running time and memory usage in terms of the input size.
\section*{Implementation Notes}
\begin{itemize}[leftmargin=*]
\item Mention any non-obvious implementation detail that is easy to get wrong.
\item Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.
\end{itemize}
\end{document}
#include <bits/stdc++.h>
using namespace std;
namespace {
void solve() {
// Fill in the full solution logic for the problem here.
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}