ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1464. Light

How to avoid TLE?
Posted by Vedernikoff Sergey 29 Aug 2006 01:42
Some people claimed, that this problem can be solved in O(NlogN). How? My solution O(N^2) gets TLE #39...

Thanks in advance!
Re: How to avoid TLE?
Posted by Ilya Rasenstein (Lyceum #40) 18 May 2007 19:09
use heap.
Re: How to avoid TLE?
Posted by AlMag 18 May 2007 21:57
What do you mean?
Re: How to avoid TLE?
Posted by Denis Koshman 27 Aug 2008 09:38
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.
Re: How to avoid TLE?
Posted by Al.Cash 9 Aug 2009 21:20
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
Re: How to avoid TLE?
Posted by Radi Muhammad Reza 17 Aug 2012 06:38
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);
    }
Re: How to avoid TLE?
Posted by Radi Muhammad Reza 17 Aug 2012 15:15
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 :)