11144 - S.O.S.

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

Moderator: Board moderators

Post Reply
liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

11144 - S.O.S.

Post by liulike »

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

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

Post 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

fernando
New poster
Posts: 21
Joined: Sat Mar 18, 2006 8:21 pm

Post by fernando »


Two buildings are neighbor if their minimum distance be less than 30 (meters).
How to determine this mnimum distance between the polygons?

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

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

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

Post by shanto86 »

Output from AC code:

Code: Select all

0 1 2 3
0
2
Self judging is the best judging!

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

Post 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.
Self judging is the best judging!

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

Post by liulike »

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

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

Post by shanto86 »

well.. i used:

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

to avoid some precission error. u may try it.
Self judging is the best judging!

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

Post by liulike »

Thanks:)

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

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

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

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian »

//cut off
Last edited by arsalan_mousavian on Fri Nov 10, 2006 6:36 pm, edited 1 time in total.
In being unlucky I have the record.

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

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

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post 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... :roll:

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by Erik »

Hello,

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

Cu, Erik :)

Post Reply

Return to “Volume 111 (11100-11199)”