Some people claimed, that this problem can be solved in O(NlogN). How? My solution O(N^2) gets TLE #39...

Thanks in advance!

use heap.

What do you mean?

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 :)