Problem with Beecrowd 1468-balloon.cpp #27
Description
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:
