OJ Board

Posted: **Wed Oct 06, 2004 8:08 pm**

The problem statement doesn't state anything about the possibility of multiple solutions, which causes me to believe that the input should only contain cases where the solution is unique.

But unless I've made some mistake, my asserts tell me otherwise.

So could anyone clarify this point? Should I handle multiple solutions some way, or have I made a mistake when I probe for occurences of such cases?

Posted: **Wed Oct 06, 2004 10:09 pm**

I just selected the solution where my calculated angle had minimum difference to given angle.
By the way, how did you check for multiple solutions?

Posted: **Thu Oct 07, 2004 7:09 am**

Hi!

But how can there be multiple solutions?

There only might be case where there is no solution if the given angle is wrong, but I assumed that the given data is correct. I just directly calculate the coordinates and print'em without any check for their consistency with the input values.

Hope it helps.
Andrey.

Posted: **Thu Oct 07, 2004 9:18 am**

Perhaps I have some fundamental misunderstanding of the problem, but for instance, for the case

Code: Select all

101336342800 339648 8 43121848 1.635755429213964e-07

I think that there are (at least) the two solutions

Code: Select all

101250099104 339648 (using b = 5390231 and a = 8)
50625049552 169824 (using b = 10780462 and a = 4)

Both are at the same angle, so it's impossible to determine which of them is the "best" that way.

I check for multiple solutions by trying different ways to factor ab into a and b, and for each solution I find, I check that it is the same as the previous solution (or that it is the first solution).

Posted: **Thu Oct 07, 2004 12:48 pm**

I think the angle you give is wrong.
For your test case, I get following two solutions for a and b:
a = 5390231 b = 8 5.6922657502e-12
a = 10780462 b = 4 1.2777448241e-11
(the third number is smallest angle)
Here are the coordinates of first and second tree, respectively, if I print them without scaling:
2350 5307 6357 14356
1175 10614 1416 12791
and that is my overall answer:
122121073536 409312

Posted: **Thu Oct 07, 2004 7:12 pm**

Ah! I didn't think about the guarantee that phi would be the smallest angle to a visible tree. I guess that changes things, I'll just have to think a while about exactly how it changes things.

Thanks.

Posted: **Thu Oct 07, 2004 8:31 pm**

FINALLY I managed to get AC (yay, I made 1400!

).

I'm not sure, but I think I've spent at least 50 submissions on this problem - most caused by being stupid.

Posted: **Wed Apr 20, 2005 12:34 am**

How did you solve it?

For the input you gave, I get the two different solutions as well.
What was the problem?

Posted: **Tue Aug 07, 2007 2:52 pm**

Hi,

Sorry for reviving such an old topic, but...

I am getting many WAs. Can I assume that a, b are integers? Or a*d, b*d are integers? Could anyone give me some further hints? Or some test cases? Thanks in advance.

For the cases discussed in posts above, I get the following result:

Code: Select all

101336342800 339648 8 43121848 1.2777448241e-11
101336342800 339648 8 43121848 5.6922657502e-12
-1 1 -1 1 1.000000000000000e-8

Code: Select all

122121073536 409312
274125587736 918784

I think they are correct.

Posted: **Tue Aug 07, 2007 8:50 pm**

I change my epsilon to 1e-10 somewhere and get Accepted!! 58 of the 397 submissions to date are by me...

My Accepted code supposes a, b are integers.

Posted: **Sat Aug 25, 2007 11:30 am**

Amazing how insight can strike suddenly. I must have looked at this problem over 20 times in the past 3 years, without any idea of how to solve it.
This must be the most obfuscated problem in the problemset, which is a big credit for its setter

.

OJ Board

10636 - Stretching Geometry

10636 - Stretching Geometry

Well I am having the same problem you were having (to Per)