10636 - Stretching Geometry

[Per]

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?

[Adrian Kuegel]

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?

[Andrey Mokhov]

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.

[Per]

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).

[Adrian Kuegel]

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

[Per]

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.

[Per]

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.

[jaredjohnson]

How did you solve it?

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

[Observer]

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.

[Observer]

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.

[little joey]

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 .