Posted: Fri Sep 08, 2006 9:08 am
how is it possible with O(n^2), i think you need to have O(n^2 lg n)
But anyway, my O(n^2 lg n) solution takes about 0.4 secs.
But anyway, my O(n^2 lg n) solution takes about 0.4 secs.
IMO complexity analysis for this problem is not easy and I believe most big-ohs reported in this thread are not true, so don't be blinded by them. Bottom line is the time you get from the judge, and I think 0.4 seconds is not too bad.
PS. I tried to analyse my solution, but couldn't get it quite right. I believe it's O(N^3.lnN), but part of it relies on probabilistics, and then it gets over my head... Also the amount of 'noise' (points that don't lie on any polygon) has a big influence on the runtime; and only the problemsetter nows how much he put in. So my suggestion is: don't bother.