10355 - Superman

[Stefan Pochmann]

Not yet in the problemset, but from the latest online contest: The Superman problem, where he jumps over buildings. For the second example, I get an angle of 67.08 instead of 67.07. Can anybody explain to me how to get to the 67.07? In particular, I'd be interested in seeing a solution that computes 67.07 without treating this example hardcodedly with extra code like I did in the contest.

[LittleJohn]

My program produced the same output as yours..Maybe it was a misjudge?

[Stefan Pochmann]

I spoke to somebody from Waterloo (where the problem was used four years ago) and he said that they don't care about little errors like that, so that in their local contest we would've gotten our solutions accepted... Still, I'd like to know if anybody has written a program that calculates the example output. It has to have some origin, right? Somebody long ago calculated that value.

[gvcormac]

You are correct. 67.08 is more accurate than 67.07

The orignal judge's solution produced 67.07 when it used a loose tolerance (.01)
on its numerical solution. This value was used in the sample to illustrate that
"within .01" was good enough.

When you decrease the judge's solution tolerance to .001 it gives 67.08

Note that in the Web directory for the judges' data for this contest, there is the
following README file:

For question C, your ouptut may differ by .01

I suggest that a checker program is appropriate. Barring that, the sample
output and judges' data should be changed.

[Red Scorpion]

Hello everyone.

I tried to solve this problem, but got WA - maybe precission error problem.
I used the formula:

Code: Select all

s = u.dp +- sqrt((u.dp)^2 - |dp|^2 + r^2)

to find the length through sphere region.
s = length to sphere region.
u = 'normalize' vector starting and ending superman's path.
dp = vector between sphere and starting position (vsphere-vstart)
r = radius of sphere.

Did I make a mistake?

regards,
RS

[Red Scorpion]

I'm sad no body help me...

How to avoid using sqrt, since my equation is like this:

Code: Select all

                      superman path through sphere 
percentage =  --------------------------------------   
                             total superman path
                      sqrt(s1) + sqrt(s2) + sqrt(s3) + ....
                 = ---------------------------------------------
                           sqrt((x2-x1)^2 + (y2-y1)^2)

Thanks.
RS

[lighted]

I am more and more getting enjoy of solving problems using bisection method.
I think that many problems of computational geometry can be solved by bisection method while have other possible solutions.

[facug91]

Hi everybody! I've been trying to solve this problem, and I think I tried all possible inputs, and still WA. I've test it with another AC code on the internet, and all test cases (I thought) had exactly the same output. If someone has some other test to try, would be great.
My code is a bit long, but is for better understanding when I have to debbug it:

Code: Select all

Remove after AC.

[lighted]

Input

Code: Select all

Dhaka
10 12 11 12 10 11
2
16 10 10 5
25 10 10 6
Rio
10 10 10 30 10 11
1
20 10 5 10
Dhaka2
10 11 12 12 10 10
2
15 10 10 5
25 10 10 5
Rio2
10 10 10 20 10 11
1
20 10 5 10
Dhaka3
1 2 3 5 5 5
2
1 1 10 5
2 1 0 6
Rio3
1 2 3 15 10 3
1
20 10 5 10

Acc Output

Code: Select all

Dhaka
41.42
Rio
83.46
Dhaka2
82.40
Rio2
85.76
Dhaka3
77.19
Rio3
31.86

Don't forget to remove your code after getting accepted.

[facug91]

Thank you so much lighted, it was just a ".y" where I should put ".z" hahaha