149 - Forests

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sat Jul 01, 2006 9:00 am

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 :evil:
Self judging is the best judging!

harrym
New poster
Posts: 5
Joined: Thu Sep 07, 2006 8:48 pm

[resolved] 149 not even close

Post by harrym » Thu Sep 07, 2006 8:52 pm

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.
Last edited by harrym on Sun Apr 08, 2007 11:33 pm, edited 1 time in total.

DIR EN GREY
New poster
Posts: 12
Joined: Thu Nov 09, 2006 11:49 am

Post by DIR EN GREY » Wed Nov 15, 2006 5:28 am

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)
Do you understand my English???

wfuny
New poster
Posts: 5
Joined: Fri May 12, 2006 3:06 pm

Post by wfuny » Tue May 08, 2007 1:13 pm

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue May 08, 2007 5:13 pm

wfuny wrote: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
New poster
Posts: 5
Joined: Fri May 12, 2006 3:06 pm

Post by wfuny » Wed May 09, 2007 2:36 pm

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. :cry:

rafastv
New poster
Posts: 22
Joined: Tue Jun 19, 2007 3:18 am

Re: 149 - Forests

Post by rafastv » Thu Jul 27, 2017 3:15 am

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!
Last edited by rafastv on Thu Jul 27, 2017 5:14 pm, edited 2 times in total.

rafastv
New poster
Posts: 22
Joined: Tue Jun 19, 2007 3:18 am

Re:

Post by rafastv » Thu Jul 27, 2017 5:09 am

wfuny wrote:
Tue May 08, 2007 1:13 pm
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.

Post Reply

Return to “Volume 1 (100-199)”