BWINF 37.2 - Lisa rennt

C#/WPF tool for task 1 of the 37th German federal CS competition, round 2.

Lisa runs 15 km/h, bus drives 30 km/h up the y-axis, leaves (0,0) at 7:30. Polygonal obstacles block the way. Find when she must leave home and which path to take.

Shortest path = straight segments between obstacle vertices (visibility graph). Last segment hits the street at 30°.

How it works

Visibility graph (naive, O(n³)). Generate all candidate edges: chords inside each obstacle (SetzeInnenstrecken), edges between different obstacles and from the start point (SetzeAussenstrecken). Discard any that intersect an obstacle edge (Kollision, 2×2 matrix intersection). Remove chords that fall outside their polygon (PunktInPolygon, ray casting).

Street edges. Each vertex gets a street intercept point at the optimal angle. Edge weight = Lisa's run time minus bus travel time to that point. A sink vertex collects these edges with the remaining bus time baked in as fake distance.

Shortest path. Standard Dijkstra on the visibility graph from start to sink. Lisa's running distance = distance of the second-to-last vertex. Departure time follows from that.

UI. Loads example files, draws obstacles, visibility graph, and the computed path. Two small demos (collision, point-in-polygon) are included.

Usage

Open a file from the menu (examples/lisarennt1.txt .. lisarennt5.txt). The computed route and departure time are shown.