| Show all threads Hide all threads Show all messages Hide all messages | | Some review | Igor Parfenov | 1464. Light | 28 Jul 2026 11:13 | 2 | The idea of problem is pretty interesting. But for me it was implementation hell. Made it with almost 1st submit, so I'll describe my way of avoiding "implementation hell".
First of all obvious things: x[i] -= x0, y[i] -= y0, so origin is at zero. x[n]=x[0], y[n]=y[0] to reduce amount of 'if's.
Second, all that we love with precision maths. I.e.
a == b --- fabs(a-b)<eps
a > b --- a > b + eps
a >= b --- a > b - eps
eps=1e-8 is enough here, but I did it without trigonometry
The main idea is that every segment covers some range of angles [a1;a2], so we have a set of "control points" of the form "angle;seg-i-start", "angle;set-i-end". So when you have this set of control points, segments will not change their relative order between two consecutive control points which can be checked by intersecting a ray and checking square of distance.
Now on how to avoid trigonometry in these and other problems like convex hull - just store vectors (segment endpoints). When comparing them for an "angle", first check the side. Let side=0 be the [0;pi) range - that is 'dy>0 || dy==0 && dx>0', then side=1 goes for [pi;2pi) range. Then you just compare sides, and if side is the same, check the sign of cross product for comparison. You will also need a special record for 2pi (side=2), I coded it as dx=0,dy=0, but be careful to treat it as (1,0) when raycasting later.
Now, ignore segments which contain origin in negative subplane (or on zero, i.e. no control points for them). Then the only thing to be dealt with is crossing 2pi-0 boundary. Criteria here is 'y[i]<0 && y[i+1]==0' - then it starts at (x[i];y[i]) and ends at (0;0). Or 'y[i]<0 && y[i+1]>0' then it starts at (x[i];y[i]), ends at (0;0), then starts at (1;0) and ends at (x[i+1];y[i+1]). These are just for 'angular' sorting of control points.
After that you will have first control point at (1;0) (angle=0) and last control point at (0;0) (angle=2pi). The rest is just running through them. Pick all control points which are 'equal' on that angular criteria, and process them - i.e. add/del corresponding segments to the heap according to px[i];py[i] ray intersection length for that control point. Let the next control point which is 'greater' according to angular criteria be 'j', after that pick topmost (nearest) segment from the heap, get intersection with px[i];py[i] ray, and px[j];py[j] ray (here don't forget to treat 0;0 as 1;0). After that add their cross product to the answer. | | WA/RE18 | Solver | 1464. Light | 27 Jul 2026 12:19 | 1 | There is a segment whose extension contains the origin | | ests | andreyDagger`~ | 1464. Light | 1 May 2025 03:48 | 1 | ests andreyDagger`~ 1 May 2025 03:48 0 0
16
1 1
2 1
2 0
3 0
3 1
2 2
3 2
4 1
4 3
0 3
0 4
1 4
1 5
-1 5
-1 -1
1 -1
12.00000000000000000000
0 0
5
-1 -1
1 0
0 -1
2 -2
2 4
5.50000000000000000000
0 0
17
-1 -1
5 -1
1 0
1 1
2 2
2 1
3 1
3 3
4 4
4 3
5 3
5 5
0 5
0 6
6 6
6 7
-1 7
24.00000000000000000000
0 0
4
0 -1
1 0
0 1
-1 0
2.00000000000000000000
0 0
4
-1 2
-1 -1
1 0
3 -1
3.6666666666
0 0
3
-1 -1
1 -1
0 1
2.00000000000000000000
0 0
11
0 -1
3 0
2 2
1 1
2 3
0 4
0 3
-1 5
-2 3
0 2
-1 0
10.50000000000000000000 | | 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 'Goryinyich' Sergey (HSE: АОП) | 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 | 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. |
|
|
