809 - Bullet Hole

[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]

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

[bodhi]

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

[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]

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]

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]

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.