My code in Cross the Lines (https://www.codingame.com/training/expert/cross-the-lines) is getting 93% completion after submit. Apparently I only fail “TriangleSquareTriangle”.
Does anybody know what the input and expected output for this testcase is?
Never mind, found my bug. By the way, it’s probably something like
“5 0 5 10”,
“15 0 15 10”,
“15 0 5 0”,
“5 10 15 10”,
“0 5 5 0”,
“20 5 15 10”,
“5 10 0 5”,
“15 0 20 5”
1 Like
Currently I have the following algorithm:
- Count the number n of segments.
- List all polygons with an odd number of sides that enclose a connected region of the plane, including the “outer polygon” that “encloses outer plane” if it’s odd, but excluding other redundant polygons.
- Count the number o of these odd polygons.
- Construct the graph of odd polygons, ie, the graph whose nodes are the odd polygons, with two nodes connected iff those two polygons share and edge.
- Construct a maximum matching and call m its size.
Then the optimal number of crossings is n + o - m.
One crossing per line, plus one extra crossing per odd polygon, but two adjacent odd polygons can share their extra crossing.
(I’m not entirely convinced that this formula is correct in all situations, but it seems to be correct on the examples.)
I cheated and simply constructed a maximal matching instead of a maximum matching, which is suboptimal in theory. But it seems that on all examples, the graph is simple enough that the maximal matching happens to be a maximum matching by chance.