Hello!
Regarding this line sweep problem with the editorial here my code is getting run time error on the last test case. I contacted the team support from the online judge Kattis but they did not allow me to see the test case where my code fails.
Can someone spot any mistake in my code I possibly made?
Thanks a lot in advance!
EDIT: In another submission (code here) when adding "if(it==mx1.end()) continue;" in line 180 I get WA instead of RE. Plus if I loop over all elements of the multiset when set.find fails (fail = returns set.end()) I get TLE as in this code. By looping over all elements the code seem to find the segment I want, but by a "manual" manner that is not fast enough. I only get the mentioned errors in the last test case that was created by the Kattis (not created by original author — a link I left on the comments may be useful to understand the situation). Also just so you know, kattis does not allow me to share the code straight from my account there, so I need to do it by pastebin.
Use google to find testcases
https://ncpc.idi.ntnu.no/ncpc2013/
Actually my code works for the test cases from the original contest. The thing is that Kattis changed the test cases because they thought it was too weak and allowed buggy code to be accepted. Here is my conversation with the support team
Possible problem: you're using multiset with comparator
cmp1
which compares bylong double x()
without applying EPS.On the other hand you use
x()
only for comparison in multiset, and it looks likea.x() < b.x()
can be rewritten using only integer comparison.Tryed it and still got RE, as in here
Long double should work because the smallest diference between two quotients of magnitude 10^n is 1/(10^(2n)) (where n is 6 in the problem, and long double has 18 significant figures)