Звучит как интересная задачка. Давай условия и формат ввода – я быстро соберу оптимальную, с кэшированием, которая будет работать не хуже, чем O(n log n). Если там есть какие-то особенности, типа карт местности или обновлений в реальном времени, говори.

Here’s a practical way to get the job done without turning the whole thing into a physics engine. The trick is to keep the geometry local – you never look at every square for every unit, you only look at the squares that actually overlap the unit’s bounding box, and then you shrink that list to the exact ones that the line really hits. --- ### 1. Spatial index – an interval tree on the X‑axis * Build a segment tree (or interval tree) keyed on the X‑interval `[leftX , leftX+side]` of each square. * Each node stores the squares whose X‑interval fully contains the node’s interval, sorted by their Y‑interval `[leftY , leftY+side]`. * Construction takes `O(m log m)` and the tree has `O(m)` nodes. --- ### 2. Query a unit’s path For a unit `U` with start `(sx,sy)` and goal `(gx,gy)`: 1. **Bounding box** `xmin = min(sx,gx)`, `xmax = max(sx,gx)` `ymin = min(sy,gy)`, `ymax = max(sy,gy)` 2. **Collect candidate squares** * Query the X‑interval tree for all squares whose X‑interval overlaps `[xmin,xmax]`. * For each returned square, check the Y‑interval against `[ymin,ymax]`. * The number of candidates is on average small (the tree prunes most of the 200 k squares). 3. **Compute intersection intervals** For each candidate square: * Solve for the parameter `t` along the segment `P(t) = (sx,sy) + t·(dx,dy)` where `dx = gx‑sx`, `dy = gy‑sy`, `0≤t≤1`. * Intersect the line with the four sides of the square to get entry and exit `t` values (or determine that there is no intersection). * If there is an intersection, store the pair `(t_entry, t_exit)`. 4. **Merge intervals** * Sort all `(t_entry,t_exit)` pairs by `t_entry`. * Merge overlapping intervals – this gives the exact portions of the path that pass through at least one square. * The complementary intervals are free‑speed. 5. **Compute time** * Let `L` be the total Euclidean length of the segment. * For each merged interval `[a,b]` the travelled length is `len = (b‑a)·L`. * Time for that part = `len / (speed·0.8)`. * Sum over all parts plus the free parts: `time = Σ free_len / speed + Σ slowed_len / (speed·0.8)`. 6. **Round to two decimals** and output. The per‑unit cost is `O(k log k)` where `k` is the number of candidate squares that overlap the bounding box – usually a handful, so the overall complexity stays near `O((n+m) log m)`. --- ### 3. Handling online updates When a new terrain feature arrives: * Insert its X‑interval into the interval tree (balanced BST insertion). * Insert the square into the Y‑lists of all nodes whose interval it covers. * In practice this is `O(log m)` per insertion, so online updates do not blow up the complexity. --- ### 4. Rough Python sketch ```python import math from bisect import bisect_left, bisect_right class IntervalTree: def __init__(self, intervals): # intervals: list of (x_left, x_right, square) intervals.sort(key=lambda iv: iv[0]) self.mid = len(intervals)//2 self.center = intervals[self.mid][0] left = intervals[:self.mid] right = intervals[self.mid+1:] self.squares = [iv[2] for iv in intervals if iv[0] <= self.center <= iv[1]] self.left = IntervalTree(left) if left else None self.right = IntervalTree(right) if right else None def query(self, x0, x1, results): if x0 <= self.center <= x1: results.extend(self.squares) if self.left and x0 <= self.center: self.left.query(x0, x1, results) if self.right and x1 >= self.center: self.right.query(x0, x1, results) class Square: def __init__(self, lx, ly, side): self.lx, self.ly, self.rx, self.ry = lx, ly, lx+side, ly+side def intersect_segment_square(sx,sy,gx,gy, sq): # Liang–Barsky algorithm for axis aligned rect dx, dy = gx-sx, gy-sy p = [-dx, dx, -dy, dy] q = [sx - sq.lx, sq.rx - sx, sy - sq.ly, sq.ry - sy] u1, u2 = 0.0, 1.0 for pi, qi in zip(p,q): if pi == 0: if qi < 0: return None else: t = qi / pi if pi < 0: u1 = max(u1, t) else: u2 = min(u2, t) if u1 > u2: return None return u1, u2 def unit_time(unit, tree): sx,sy,sp,gx,gy = unit xmin, xmax = min(sx,gx), max(sx,gx) ymin, ymax = min(sy,gy), max(sy,gy) candidates = [] tree.query(xmin, xmax, candidates) intervals = [] for sq in candidates: if sq.ly > ymax or sq.ry < ymin: continue res = intersect_segment_square(sx,sy,gx,gy,sq) if res: intervals.append(res) intervals.sort() merged = [] for a,b in intervals: if not merged or a > merged[-1][1]: merged.append([a,b]) else: merged[-1][1] = max(merged[-1][1], b) L = math.hypot(gx-sx, gy-sy) time = 0.0 last = 0.0 for a,b in merged: free_len = (a-last)*L time += free_len / sp slowed_len = (b-a)*L time += slowed_len / (sp*0.8) last = b free_len = (1-last)*L time += free_len / sp return round(time,2) # Read input, build tree, loop over units printing times ``` --- That’s all the heavy lifting. With the interval tree you avoid the quadratic blow‑up, the Liang–Barsky intersection is fast, and the online insertions stay cheap. Give it a try and tweak the constants – the big‑O stays clean, and you’ll see the numbers drop quickly. Happy coding!