809 - Bullet Hole

All about problems in Volume 8. 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
bodhi
New poster
Posts: 2
Joined: Sun Nov 03, 2002 3:31 pm

809 - Bullet Hole

Post by bodhi »

Hi

I've bee trying to solve this for days (each time getting a WA). Is there something special about this problem?
What means "... two real numbers are considered equal if they are less than 10e-6 apart"? Does one have to write something like this:

int equal(double a, double b)
{
return a-b >= -1e-6 && a-b <= 1e-6
}

?

Thanks a lot

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

It means:
fabs(a-b)<1e-6

bodhi
New poster
Posts: 2
Joined: Sun Nov 03, 2002 3:31 pm

Post by bodhi »

That looks much nicer, thank you.
But do you actually use this, for problems involving floating point?

SnapDragon
Problemsetter
Posts: 22
Joined: Tue Jun 11, 2002 12:35 am

Post by SnapDragon »

I avoided using floating point whenever possible. I determine whether the ray intersects individual cubes wholly with integer arithmetic; the only doubles I use are for calculating how high up on the cube the intersection point is.

You have to remember a few important facts about fluid dynamics. Suppose one subcube is punctured at height 0.5, and then the next subcube at height 0.6, before the bullet leaves the cube. Due to water pressure, BOTH cubes will lose the top 0.4 of their water - even though the inner cube's puncture is lower than the outer cube's.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

SnapDragon wrote:You have to remember a few important facts about fluid dynamics. Suppose one subcube is punctured at height 0.5, and then the next subcube at height 0.6, before the bullet leaves the cube. Due to water pressure, BOTH cubes will lose the top 0.4 of their water - even though the inner cube's puncture is lower than the outer cube's.
That is what you have to believe in order to get this problem AC (probably, I haven't solved it yet), but it's not true in real life. No water can leave a cubicle unless an equal amount of air can enter the cubicle to fill up the void. Since the water level in the second cubicle is 0.6, no air can flow into the first cubicle, because it's hole is at 0.5, so the first cubicle remains completely filled.
So in real life, when the gun is fired from within the cube in an upward direction, only the cubicles that share the 'exit wound' can lose water.

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

Post by minskcity »

That's not entirely correct. The air only needs to replace the water inside if there is air pressure from outside. If there is no air pressure (and in most UVA problems you don't account for air pressure) your argument is not valid. Moreover, if there is pressure, the water still go down once the z-coordinate difference between the top of a small cube and the most outer hole reaches certain treshold (in the case of water/pressure at sea level that treshold is around 10 meters).

gt1404
New poster
Posts: 6
Joined: Sat Dec 26, 2009 10:16 am

convinced my algorithm is correct

Post by gt1404 »

Can anyone run this test case for me:

Code: Select all

5   25     5  15   0     5  15 100
 3   30     0 -35   0     3 -25   3
10   16     8  17  11    12  19   6
10 100 5 5 150 5 5 145
1 10 9 9 4 9 9 6
2 10 9 9 4 9 9 6
2 10 9 9 -4 9 9 6
2 10 9 9 20 9 9 40
2 10 -10 1 5 0 1 5
2 10 6 5 -10 6 5 5
2 10 5 5 -100 5 5 0
2 10 -3 3 5 0 3 5
1 10 0 4 3 0 4 8
 0
My output:

Code: Select all

Trial 1, Volume = 2500.00

Trial 2, Volume = 1950.00

Trial 3, Volume = 0.00

Trial 4, Volume = 10000.00

Trial 5, Volume = 0.00

Trial 6, Volume = 125.00

Trial 7, Volume = 250.00

Trial 8, Volume = 0.00

Trial 9, Volume = 250.00

Trial 10, Volume = 500.00

Trial 11, Volume = 1000.00

Trial 12, Volume = 250.00

Trial 13, Volume = 700.00
Thanks in advance.

Post Reply

Return to “Volume 8 (800-899)”