I think you are wrong. My AC program prints 16 too

Edited by author 06.07.2011 11:00

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);
    }