## 809 - Bullet Hole

Moderator: Board moderators

### 809 - Bullet Hole

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
bodhi
New poster

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

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

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

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

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

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

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

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.

little joey
Guru

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

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).
minskcity
Experienced poster

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

### convinced my algorithm is correct

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   310   16     8  17  11    12  19   610 100 5 5 150 5 5 1451 10 9 9 4 9 9 62 10 9 9 4 9 9 62 10 9 9 -4 9 9 62 10 9 9 20 9 9 402 10 -10 1 5 0 1 52 10 6 5 -10 6 5 52 10 5 5 -100 5 5 02 10 -3 3 5 0 3 51 10 0 4 3 0 4 8 0`

My output:
Code: Select all
`Trial 1, Volume = 2500.00Trial 2, Volume = 1950.00Trial 3, Volume = 0.00Trial 4, Volume = 10000.00Trial 5, Volume = 0.00Trial 6, Volume = 125.00Trial 7, Volume = 250.00Trial 8, Volume = 0.00Trial 9, Volume = 250.00Trial 10, Volume = 500.00Trial 11, Volume = 1000.00Trial 12, Volume = 250.00Trial 13, Volume = 700.00`