149 - Forests

[shanto86]

Thanks mf i have just got AC. and yes you are right only i checked till 21.

but there was one another problem which i removed by looking at other posts at the group, and that is:

now.from=temp1 - thita - (0.005*PI/180);
now.to =temp1 + thita + (0.005*PI/180);

that extra part at the end, these types of precision problem is really annoying

[harrym]

Any ideas why my attempt at 149 is so far off? (returns 88 for given test case)

Code: Select all

Everyone loves a good precision error right?

works by breaking all points (-20, .. 21) into 4 quadrents then sorting by distance and checking each point for occlusion by all points in same quadrant with smaller distance (from x,y) seems simple enough especially since they give you the desired EPSILON value and yet here i am unable to get even the given case right.

[DIR EN GREY]

hi harrym.

I'll show you which tree can be visible in sample input case. I hope this helps you. Points have beeen sorted by distance between tree and observer.

Code: Select all

visible: (0,0)
visible: (1,0)
visible: (0,1)
visible: (1,1)
visible: (0,-1)
visible: (1,-1)
visible: (-1,0)
visible: (2,0)
visible: (-1,1)
visible: (2,1)
visible: (0,2)
visible: (1,2)
visible: (2,-1)
visible: (-1,2)
visible: (0,-2)
visible: (1,-2)
visible: (-2,0)
visible: (-2,1)
visible: (3,0)
visible: (3,1)
visible: (0,3)
visible: (1,3)
visible: (-1,-2)
visible: (-2,-1)
visible: (2,-2)
visible: (3,-1)
visible: (-2,2)
visible: (-1,3)
visible: (3,2)
visible: (2,3)
visible: (0,-3)
visible: (1,-3)
visible: (-3,0)
visible: (-3,1)
visible: (4,0)
visible: (4,1)
visible: (0,4)
visible: (1,4)
visible: (-1,-3)
visible: (2,-3)
visible: (-3,-1)
visible: (4,-1)
visible: (4,2)
visible: (-1,4)
visible: (2,4)
visible: (-2,-3)
visible: (3,-3)
visible: (-3,3)
visible: (0,-4)
visible: (4,3)
visible: (1,-4)
visible: (3,4)
visible: (-4,1)
visible: (5,1)
visible: (0,5)
visible: (1,5)
visible: (-4,-1)
visible: (-4,2)
visible: (5,-1)
visible: (-2,-4)
visible: (3,-4)
visible: (-4,3)
visible: (5,3)
visible: (3,5)
visible: (1,-5)
visible: (-5,1)
visible: (-1,-5)
visible: (6,1)
visible: (-3,-4)
visible: (2,-5)
visible: (4,-4)
visible: (1,6)
visible: (-5,2)
visible: (-4,4)
visible: (6,2)
visible: (5,4)
visible: (2,6)
visible: (-5,-2)
visible: (6,-2)
visible: (-2,6)
visible: (3,6)
visible: (-5,-3)
visible: (-6,1)
visible: (-1,-6)
visible: (7,1)
visible: (-3,6)
visible: (-6,-1)
visible: (4,6)
visible: (-1,7)
visible: (-2,-6)
visible: (-6,-2)
visible: (7,-2)
visible: (-4,-5)
visible: (5,-5)
visible: (-2,7)
visible: (3,7)
visible: (-5,5)
visible: (6,5)
visible: (4,-6)
visible: (-6,4)
visible: (7,4)
visible: (-7,-1)
visible: (-7,2)
visible: (8,-1)
visible: (8,2)
visible: (-4,-6)
visible: (5,-6)
visible: (-6,5)
visible: (7,5)
visible: (8,-3)
visible: (-5,-6)
visible: (6,-6)
visible: (2,-8)
visible: (-6,6)
visible: (7,6)
visible: (8,-4)
visible: (2,9)
visible: (3,-8)
visible: (-7,5)
visible: (3,9)
visible: (6,8)
visible: (3,-9)
visible: (10,3)
visible: (-5,9)
visible: (7,-8)
visible: (11,2)
visible: (9,7)
visible: (-5,-9)

[wfuny]

Could anyone tell me why that x & y only have to count to 20??

[mf]

Could anyone tell me why that x & y only have to count to 20??

It's probably wrong, but it works well and fast enough to get accepted

If you like, you can try to construct a counter-example case, and ask to add it to the judge's tests in Bugs and suggestions forum.

[wfuny]

But If we count to maxdis=(r/sin(0.005/180*PI)) ,
suppose r=1 ,so that we have to count to 5729 ,it may get TLE.
Am I right?

and how cound you judge whether that tree is obscure or not??
count the angle of it position or slope of it position??
However,i think both of these methods will get TLE.

[rafastv]

Hi, there, some tips for you.

1) Precision matters, I've used 1e-9

2) Don't compute the angle, use cos, sin or tan.

3) Use your own PI, I've used #define PI 3.14159265358979323846264338327

4) You should not only consider trees that are too small and gaps that are too small, but beyond that when you "add" a tree to your sight you must make sure that the remaining gap allows that tree to be seen or else you should join it with its neighbors. (Most people here seems to have that problem, if you were supposed to find 61 and found 62 or instead of finding 128 you are finding 129 or 130 trees, you are most likely not considering all possible cases, this is not a precision problem!).

For instance, Imagine that the gap beyond two trees is slightly greater than 0.01 degrees (great!), you can add a valid tree, but when you add this tree the remaining gap will be smaller than 0.01 degrees. Therefore, this tree should be joined with its neighbors.

5) Don't worry about perspective, orthogonal projection is fine.

6) Make a function that adds trees around the observer first and grow his sight until he can't see any more trees (20 steps is enough).

Good luck!

[rafastv]

Could anyone tell me why that x & y only have to count to 20??

Because of the limited range of the problem (0.nn), you will be able to test all cases once you have a solution, and after 20 steps the algorithm just do updates to the sight of the trees but adds no new tree. It seems that to get AC for this problem is enough. Think of it as an Iterative method, it is a valid method applied in many math problems (like root finding), and we could go on forever actually (the gaps just keep getting smaller)...the problem states however that we can stop at 0.01 degrees or 20 steps in an ad hoc solution.

Whenever we have infinity, iterative methods are the way to go.