|
|
вернуться в форумcomplexity My solution is O(n*log n) and i wonder if there is a linear? Re: complexity Послано Walrus 21 авг 2006 21:13 My solution is O(n*log(n)) too... Re: complexity I have an idea for linear-time solution, but I didn't implement it. Walk in coutner-clockwise order. While the lamp is in positive half-plane (i.e. we face inner side of a segment), add it. Once we face outer side (i.e. lamp is in negative half-plane), we cast darkness backwards in clockwise order from i+1'th vertex of outer side. Also, there will be no light until we reach its i'th angle. So, "forwards darkness" is skipped as long as we walk counter-clockwise forwads and "backwards darkness" pointer only deceases (walks only clockwise). |
|
|