11144 - S.O.S.

liulike · Post by **liulike** » Fri Oct 27, 2006 3:03 pm

Is there any trick input for this problem? thx:)

liulike · Post by **liulike** » Fri Oct 27, 2006 5:24 pm

What's the correct output for this:

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

fernando · Post by **fernando** » Sat Oct 28, 2006 2:43 am

Two buildings are neighbor if their minimum distance be less than 30 (meters).

How to determine this mnimum distance between the polygons?

liulike · Post by **liulike** » Sat Oct 28, 2006 3:29 am

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.

shanto86 · Post by **shanto86** » Sat Oct 28, 2006 5:49 am

Output from AC code:

Code: Select all

0 1 2 3
0
2

shanto86 · Post by **shanto86** » Sat Oct 28, 2006 5:51 am

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.

liulike · Post by **liulike** » Sat Oct 28, 2006 6:53 am

Thank you!
I have considered this case, but still WA

shanto86 · Post by **shanto86** » Sat Oct 28, 2006 7:35 am

well.. i used:

ceil(10 * (A-1e-6)/B )

to avoid some precission error. u may try it.

liulike · Post by **liulike** » Sat Oct 28, 2006 3:53 pm

Thanks:)

So where did you use 1e-8 which the problem statement mentioned? Only to compare the distance with 30?

shanto86 · Post by **shanto86** » Sat Oct 28, 2006 7:18 pm

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!

arsalan_mousavian · Post by **arsalan_mousavian** » Mon Oct 30, 2006 1:17 pm

//cut off

liulike · Post by **liulike** » Mon Oct 30, 2006 6:44 pm

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.

minskcity · Post by **minskcity** » Sun Jan 07, 2007 7:59 pm

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

Erik · Post by **Erik** » Sun Apr 01, 2007 8:08 pm

Hello,

it is possible to avoid all kind of floating-point arithmetics in this task.

Cu, Erik