Page 1 of 1
11144 - S.O.S.
Posted: Fri Oct 27, 2006 3:03 pm
by liulike
Is there any trick input for this problem? thx:)
Posted: Fri Oct 27, 2006 5:24 pm
by liulike
What's the correct output for this:
Code: Select all
3
4
4 0 0 0 1 1 1 1 0
3 2 2 3 2 3 3
4 21 0 22 0 22 1 21 1
3 33 2 33 3 34 3
0
15
4
4 0 0 0 1 1 1 1 0
3 2 2 3 2 3 3
4 21 0 22 0 22 1 21 1
3 33 2 33 3 34 3
0
4
4
4 0 0 0 1 1 1 1 0
3 2 2 3 2 3 3
4 21 0 22 0 22 1 21 1
3 33 2 33 3 34 3
2
4
Posted: Sat Oct 28, 2006 2:43 am
by fernando
Two buildings are neighbor if their minimum distance be less than 30 (meters).
How to determine this mnimum distance between the polygons?
Posted: Sat Oct 28, 2006 3:29 am
by liulike
fernando wrote:
Two buildings are neighbor if their minimum distance be less than 30 (meters).
How to determine this mnimum distance between the polygons?
We use Set_A to represent all the line segments of polygon A, and Set_B to represent all the line segments of polygon B, then the minimum distance between polygon A and B is the minimum distance between any line segments in SetA and SetB.
Posted: Sat Oct 28, 2006 5:49 am
by shanto86
Posted: Sat Oct 28, 2006 5:51 am
by shanto86
well there is a tricky case but it is tough to make such. the case is like this:
say there are 4 houses. A, B, C. A is burnt initially. Then say as its neighbour it can burn B at 5min and C at 10min. But B can burn C in 3min. So C is burnt within 8 min. not 10min. so if there r 8min times then ur output have to be A B C.
Posted: Sat Oct 28, 2006 6:53 am
by liulike
Thank you!
I have considered this case, but still WA
Posted: Sat Oct 28, 2006 7:35 am
by shanto86
well.. i used:
ceil(10 * (A-1e-6)/B )
to avoid some precission error. u may try it.
Posted: Sat Oct 28, 2006 3:53 pm
by liulike
Thanks:)
So where did you use 1e-8 which the problem statement mentioned? Only to compare the distance with 30?
Posted: Sat Oct 28, 2006 7:18 pm
by shanto86
well i used 1e-6 instead of 1e-8. i think it will work for 1e-8 as well... but as A and B both may contain at most .5 so it does not matter!
Posted: Mon Oct 30, 2006 1:17 pm
by arsalan_mousavian
//cut off
Posted: Mon Oct 30, 2006 6:44 pm
by liulike
shanto86 wrote:well i used 1e-6 instead of 1e-8. i think it will work for 1e-8 as well... but as A and B both may contain at most .5 so it does not matter!
Thank you very much!
It is not the precision problem:(
Just my stupid error in computation for the area of polygon.
Posted: Sun Jan 07, 2007 7:59 pm
by minskcity
I like when problemsetters put things like
It should be noted that two floating point numbers a and b assumed equal if their absolute difference is less than 1e-8.
in the problem statements. It's like saying "my data and solution could be wrong, so I'll offset my precision erros with ambiguouty in the problem statment"
. I mean, if a problem states that 1 and 1 + 1e-8 are the same numbers, and then asks you to take a ceiling of 1, what exactly are you supposed to do? This is just the most trivial example, when you solve a problem that requires geometry routines, there are multiple ways of interpreting and using that 1e-8...
Posted: Sun Apr 01, 2007 8:08 pm
by Erik
Hello,
it is possible to avoid all kind of floating-point arithmetics in this task.
Cu, Erik
