|
|
Show all threads Hide all threads Show all messages Hide all messages | WA #35 | Vladimir Chirkov | 1464. Light | 17 Jun 2015 17:29 | 2 | WA #35 Vladimir Chirkov 17 Jun 2015 16:19 Please help me. I cann't find what is wrong. Any tests or ideas please. I found a bug. All tests are OK! | How to avoid TLE? | Vedernikoff Sergey | 1464. Light | 17 Aug 2012 15:15 | 7 | Some people claimed, that this problem can be solved in O(NlogN). How? My solution O(N^2) gets TLE #39... Thanks in advance! Sort all starts/ends by angle. Then track closest inner wall within every angular segment, use heap for that. Comparing segments in a heap can be done by comparing distance to ray intersection. Though rays will be different during segment's lifetime, relative order of segments along the ray will not change because segments do not intersect. I've implemented this approach, but I have WA#33. I make exact calcucations except finding the square of triangle in the angular segment. Can somebody help me to overcome the problems with precision? Or maybe there's some bug in my program... Edited by author 09.08.2009 21:21 Of course 2 segments compared once will never swap order; but suppose, there is an active segment in the heap whose end is not reached yet. However, another segment's start has come before in angle-wise sorted order. Now, when we enter that segment in the heap according to distance along current ray we have trouble; since, the previously mentioned segment's distance was calculated along old ray. Now, it may occur so that, the newly entered segment comes before along current ray, but previous segment might be popped before cause, its distance is less in heap - since, this is distance along old ray. And, there may be many such previous segments in the heap. I think, this gives same scenario as would be in case of intersection; and this is precisely what giving me WA 33. If, I update all existent segments in the heap by distance along current ray this gives the same effect as sorting edges each time and of course, gives me TLE 37 or 39. This is creeping me out. Sure, I am missing some trivial logic :( Please, help me out. Thanks in advance. This is part of the code I am trying on now: for(i=0;i<n;++i){ if(mark[arr[i].e1]) out(arr[i].e1); else in(arr[i].e1,(arr[i].ang+arr[i+1].ang)/2.0); if(mark[arr[i].e2]) out(arr[i].e2); else in(arr[i].e2,(arr[i].ang+arr[i+1].ang)/2.0); seg ret=heap_extract_max(); area+=triangle(make_pair(0.0,0.0),calc(ret.e,arr[i].ang),calc(ret.e,arr[i+1].ang)); in(ret.e,(arr[i+1].ang+arr[i+2].ang)/2.0); } Sorry, I did stupid mistake. I made distance of a segment along some ray an attribute of the segment structure which is inserted on heap and in operator<() I compared that attribute. That's obviously wrong; since, newly inserted segment has distance calculated along different ray and can't be compared with others that way. But, look, 'the ORDER of the all previously entered segments' is correct. So, all i have to do is, rather than making distance an attribute, compute it along current ray/angle each time operator<() is called. I think, that will fix WA 33 of anyone getting it :) | What wrong with test #41? | AterLux | 1464. Light | 19 Apr 2011 20:51 | 1 | I have no idea: my solution seems to be correct, but I got WA#41. I've checked precision, but still got WA. Please give me some tests, or describe the way I should look. | WA#29 | Hatred | 1464. Light | 4 Mar 2010 00:17 | 2 | WA#29 Hatred 4 Mar 2010 00:12 What it could be? Any tests please. Well, after I started to use double instead of float, it passed the test. | complexity | UdH-WiNGeR | 1464. Light | 27 Aug 2008 09:45 | 3 | My solution is O(n*log n) and i wonder if there is a linear? My solution is O(n*log(n)) too... 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). | help me | Semenoff | 1464. Light | 27 Sep 2006 10:37 | 1 | please write me a solution.....how to decide this problem. |
|
|
|