B. Asteroids
The year is 2115. The asteroid communication relay system was set up a decade ago by the Asteroid Communication Ministry. It is running fine except for one small problem – there are too many asteroids! The smaller ones not only keep interfering with the sig...
Problem Statement
Formatted from the contest statement text, with sample tests broken out into copyable blocks.
The year is 2115. The asteroid communication relay system was set up a decade ago by the Asteroid Communication Ministry. It is running fine except for one small problem – there are too many asteroids! The smaller ones not only keep interfering with the signals from the relay stations but they are also a danger to all the maintenance aircrafts that fly between the stations. These small asteroids must be destroyed! The Interplanetary Coalition to Prevent Catastrophes (ICPC) has been charged with removing these dangerous asteroids and has hired an elite team of hot-shot pilots for the job. Han Duo is the captain of this team of asteroid destroyers. Armed with his missiles, Han flies through the asteroid belt blowing up any asteroid that the ICPC deems a nuisance. The ICPC is having some unfortunate budgetary problems. One result of this is that Han and his team do not have as many missiles as they would like, so they cannot blow up all the troublesome asteroids. But the asteroids are small and the missiles are powerful. So if two asteroids are near each other and line up properly, it is possible to take out both with a single missile. Han’s screen displays asteroids as non-rotating two-dimensional simple convex polygons, each of which moves at a fixed velocity. He has decided that the best time to hit two asteroids is when the overlap of the two polygons is at a maximum. For example, Figure B.1, which illustrates Sample Input 1, shows two asteroids and snapshots of their subsequent positions at 1-second intervals. The two asteroids start touching after 3 seconds and the maximum overlap area occurs between 4 and 5 seconds.
Figure B.1: Sample Input 1. Two asteroids with crossing paths.Calculating when the maximum overlap occurs for two asteroids requires a bit of programming, but unfortunately Han slept through most of his coding classes at the flight academy. This is where you come in.
Input
The input consists of two asteroid specifications. Each has the form n x1 y1 x2 y2 . . . xn yn vx vy where n (3 ≤ n ≤ 10) is the number of vertices, each xi , yi (−10 000 ≤ xi , yi ≤ 10 000) are the coordinates of a vertex of the asteroid on Han’s screen given in clockwise order, and vx , vy (−100 ≤ vx , vy ≤ 100) are the x and y velocities (in units/second) of the asteroid. The xi , yi values specify the location of each asteroid at time t = 0, and the polygons do not intersect or touch at this time. The maximum length of any side of an asteroid is 500. All numbers in the input are integers.
Output
Display the time in seconds when the two polygons have maximum intersection, using the earliest such time if there is more than one. If the two polygons never overlap but touch each other, treat it as an intersection where the common area is zero and display the earliest such time. If the polygons never overlap or touch, display never instead. You should consider positive times only. Your output should have an absolute or relative error of at most 10−3 .
Sample Tests
6 3 2 2 4 3 6 6 6 7 4 6 2 2 2
4 18 5 22 9 26 5 22 1 -2 14.193518 4 0 0 0 2 2 2 2 0 -1 1
4 10 0 10 2 12 2 12 0 1 1neverEditorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
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
C++ solution used for this page.
#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 and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/icpc/2015/B-asteroids/solution.texC++ implementationcompetitive_programming/icpc/2015/B-asteroids/solution.cppStatement textcompetitive_programming/icpc/2015/B-asteroids/statement.txtStatement PDFcompetitive_programming/icpc/2015/B-asteroids/statement.pdfMetadatacompetitive_programming/icpc/2015/B-asteroids/meta.jsonYear packetcompetitive_programming/icpc/2015/contest_problems.pdf