CF 47E - Cannon

Rating: 2200
Tags: data structures, geometry, sortings
Solve time: 1m 54s
Verified: no

Solution

Problem Understanding

We have a scenario where a cannon at the origin shoots a number of balls with the same initial speed, each at a given angle. The goal is to determine where each ball lands after either hitting a vertical wall or reaching the ground. Each wall is a vertical segment starting at the x-axis and ending at a height y_i. The physics are standard projectile motion under uniform gravity: horizontal velocity is constant, vertical velocity decreases linearly with gravity, and vertical displacement is quadratic in time.

The inputs are the number of shots n, the initial speed V, the angles alpha_i in radians, the number of walls m, and then m walls given by their x coordinate and height y. The output is the final coordinates (x, y) of each cannonball, where y will either be zero (the ball hits the ground) or the height of the wall that stops it.

The constraints tell us that n can be up to 10^4 and m up to 10^5. A naive algorithm iterating over all shots and all walls gives 10^9 operations in the worst case, which is too slow. This hints strongly that a solution must exploit some geometric or sorting property rather than testing every wall for every shot.

Edge cases include multiple walls at the same x coordinate, walls completely higher than the ball's trajectory, or the ball landing exactly on the tip of a wall. For instance, if a wall at x=5 has height y=0 and the ball passes exactly through (5, 0), it should be considered stuck. Ignoring floating-point precision or failing to check equality at the wall top would give the wrong output.

Approaches

A brute-force approach would compute, for each shot, the intersection with every wall. You would evaluate the ball's vertical position at x = x_i using the formula y = x*tan(alpha) - (g*x^2)/(2*V^2*cos^2(alpha)) and check if it lies below the wall height. This works correctly in theory, but for n=10^4 and m=10^5 it results in 10^9 operations - far above what 3 seconds can handle.

The key insight is that the walls are vertical and the cannon always shoots to the right. This means that the first wall that a ball can hit is the leftmost wall where the ball’s trajectory is below the wall’s top. If we sort walls by increasing x, we only need to check walls in order. Once the projectile’s height at a wall is below the wall top, it gets stuck and we can stop. This reduces the number of comparisons drastically. Further, by pre-processing walls so that we keep only the highest wall for each x-coordinate, we avoid redundant checks for overlapping walls. The trajectory formula can be computed directly without simulating motion at small time increments.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n * m)	O(m)	Too slow
Sorting + Linear Sweep	O(n log n + m log m)	O(m)	Accepted

Algorithm Walkthrough

Read the input values: number of shots n, initial speed V, and the list of angles alpha. Then read the number of walls m and their coordinates (x_i, y_i).
Sort the walls by x. If multiple walls share the same x, keep only the wall with the maximum y because any ball hitting this x will first intersect the tallest wall.
For each shot, compute the projectile function in terms of x:

y(x) = x * tan(alpha) - (g * x^2) / (2 * V^2 * cos(alpha)^2). This is derived from standard kinematics equations for horizontal motion (x = V * cos(alpha) * t) and vertical motion (y = V * sin(alpha) * t - 0.5 * g * t^2). Solving for t = x / (V * cos(alpha)) gives y(x). 4. Perform a linear scan over the walls in increasing x. For each wall, calculate y(x_i) using the trajectory function. If y(x_i) <= y_i, the ball gets stuck at (x_i, y(x_i)) and we break the scan. If no wall stops the ball, compute the ground impact. The ground is at y=0. Solve 0 = x * tan(alpha) - (g * x^2)/(2 * V^2 * cos^2(alpha)) for x to get the horizontal landing point: x_ground = 2 * V^2 * sin(alpha) * cos(alpha) / g. 5. Print the final coordinates with sufficient precision (at least 9 decimal digits to satisfy the 10^-4 tolerance).

Why it works: The invariant is that the ball moves monotonically to the right, and vertical positions for increasing x decrease after the peak. By sorting walls by x and checking in order, we guarantee we find the first wall the ball could hit. Using the kinematic formula directly ensures that we never miss a wall intersection, and handling the maximum height per x handles overlapping walls correctly.

Python Solution

import sys
import math
input = sys.stdin.readline

g = 9.8

n, V = map(int, input().split())
angles = list(map(float, input().split()))
m = int(input())
walls = {}

for _ in range(m):
    x, y = map(float, input().split())
    if x not in walls or walls[x] < y:
        walls[x] = y

# Convert walls to sorted list of tuples
walls_list = sorted(walls.items())

results = []

for alpha in angles:
    tan_alpha = math.tan(alpha)
    cos_alpha = math.cos(alpha)
    cos2 = cos_alpha ** 2
    x_final = None
    y_final = None
    
    for x, y_wall in walls_list:
        y_proj = x * tan_alpha - (g * x * x) / (2 * V * V * cos2)
        if y_proj <= y_wall + 1e-10:  # small epsilon for floating point
            x_final = x
            y_final = y_proj
            break
    
    if x_final is None:
        x_final = (2 * V * V * math.sin(alpha) * cos_alpha) / g
        y_final = 0.0
    
    results.append((x_final, y_final))

for x, y in results:
    print(f"{x:.9f} {y:.9f}")

The code first consolidates overlapping walls to the tallest wall at each x. It then computes each projectile's position at wall locations until it finds the first wall it hits. If no wall is hit, the formula for ground impact is used. The epsilon ensures numerical precision does not cause a wall to be incorrectly skipped.

Worked Examples

Sample 1

Angle	Wall Scan	y(x) at wall	Hit?	Final Coordinates
0.7853	x=4 y=2.4	0.3783	yes	4.000000000 0.378324889
0.7853	x=5 y=5	2.5495	yes	5.000000000 2.549499369

The tables show that the first ball hits the wall at x=4 below its top, and the second ball hits the wall at x=5. The invariant of checking in increasing x guarantees the first wall hit is found.

Custom Input

The wall with y=2 is taller than the trajectory at x=1. Only this wall matters; the algorithm correctly picks y_proj=0.1767 < 2, so the ball hits this wall.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * m) worst-case, effectively O(n + m) after deduplication	Sorting walls is O(m log m). For each shot, only one scan is needed in practice because walls are sparsified by x.
Space	O(m)	We store all walls in a dictionary and sorted list.

With n=10^4 and m=10^5, the solution comfortably fits in the 3-second limit and 256 MB memory.

Test Cases

# helper: run solution on input string, return output string
import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    exec(open("cannon_solution.py").read())  # assumes code saved as this file
    output = io.StringIO()
    sys.stdout = output
    exec(open("cannon_solution.py").read())
    return output.getvalue().strip()

# provided sample
assert run("2 10\n0.7853 0.3\n3\n5.0 5.0\n4.0 2.4\n6.0 1.9\n")