Problem with Beecrowd 1468-balloon.cpp

[ChrisVilches]

Beecrowd 1468-balloon.cpp

My solution is broken for this input (but it still gets AC)

4 1
1 9 7 3
3 8 12 6
0 12 2 12
2 15 4 15
5

3 1
1 9 7 3
4 7 12 8
0 12 2 12
5

Correct answer:

1 12
1 12

My AC code returns (this answer is incorrect):

1 12
12

Solution on UDEBUG also returns this incorrect answer.

Updating the code so that it works gets Wrong Answer on Beecrowd.

This can be solved by changing the code that collects events, and use something like this (UPDATE: This code also doesn't work, a proper segment sorting is necessary):

  for (int i = 0; i < N; i++) {
    Point event_point;

    event_point.x = 0;  // Don't care
    event_point.y = min(segments[i].p.y, segments[i].q.y);

    events[ev_n++] = make_pair(event_point, i);
  }

In other words, use the lowest point instead of the exit point. This works for this case, but I don't know if this fix is correct, and there's no data to test against (official data might be broken).

The case with 3 segments looks like this:

[ChrisVilches]

• uDebug solution was updated.
• Collected all the data from uDebug plus my own test cases, and they all work correctly. uDebug also returns the same answer as mine (even for my custom test cases).
• Data compilation was stored locally on my PC.
• Ended up using the same segment sorting as kattis/pinball and kattis/directingrainfall.

TODO:

• Code review the refactored file.
• Re-submit to Beecrowd and UVA.