10760 - Translation or rotation

[w k]

Hi,

What is the correct output for:

10 10 10.0000001 10 20 10 20.0000001 10

Is it:

"Translation by vector <0.0,0.0>."

or just

"No move."


Wojciech

[david]

Hi.
The correct output is "Translation by vector <0.0,0.0>."
You should only print "No move" when the coordinates of the endpoints coincide to within 10e-8.

[w k]

Hi,

Could anybody post some interesting I/O?

Wojciech

[w k]

Since nobody gives I/O I guess that there are no interesting I/O for this problem!

Wojciech

[shamim]

Can anybody give me some hint?

I tried to solve it by considering the point of rotation as the centre of circle with the translating points lieing on two circles with this same centre. I could not get the third sample right.

[Cho]

I tried to solve it by considering the point of rotation as the centre of circle with the translating points lieing on two circles with this same centre. I could not get the third sample right.

There are many degenerated cases to handle for rotation. But for the third sample, my AC code works the same as yours. It finds the intersection of the perpendicular bisector of (2.1,0) and (0,2.1) and the perpendicular bisector (3,1) and (-1,3). This intersection is (0,0) and the rotation angle is 90 degrees.

What output do your get for the third sample?

[..]

It finds the intersection of the perpendicular bisector of (2.1,0) and (0,2.1) and the perpendicular bisector (3,1) and (-1,3). This intersection is (0,0) and the rotation angle is 90 degrees.

Hi Cho,

Is that all your algorithm? For example,
0 1 1 2 0 0 2 2
The 2 the perpendicular bisector are the same line (y = 2 - x)

I try to solve in this way but WA

Code: Select all

if 2 prependicular bisector has only one intersection
   take that as the rotation point
else if the 2 line segments have only one intersection when extraplot to both side
   take that as the rotation point
   /* for the case 0 1 1 2 0 0 2 2 */
else
   take the mid-point between a and a' as rotation point.
   /*  I can only find the case like 1 0 -1 0 2 0 -2 0 falls in this part*/

Could anyone tells me what's wrong?? Thanks!

[Cho]

hi ..,
can you handle cases like these:
1 1 1 1 1 2 2 1 (a=a', so it's perpendicular bisector is undefined)
1 2 2 1 1 1 1 1 (b=b', ...)

[..]

I can handle that, when a=a'(b = b'), we should take that as rotation point, right?

[Cho]

Then what we did should be essentially the same.
Here is my workflow for rotation:

Code: Select all

if a=a'
   rotate about a
else if b=b'
   rotate about b
else if a, b, a', b' are colinear
   rotate about (a+a')/2 by 180 degree
else if segment a,a' is parallel to segment b,b'
   rotate about intersection of extension of a,b and extension of a',b'
else
   rotate about intersection of perpendicular bisector of a,a' and perpendicular bisector of a',b'

btw, for all the output, i print the value+1e-9 to avoid rounding error to strange result (e.g. negative zero -0.0)
And one more source of error, 0 0 0 0 0 1 1 0 should be 270 degree instead of 90

[..]

Cho, thanks for the help.
I find that I made stupid mistake in implementation, both of our pseudo code are correct.

[Destination Goa]

Actually it is bad practice to give coordinates of segments when their lengths should be equal. Also it is bad practice to use same threshold (epsilon) value for all comparisons. Square terms have different precision. E.g. I had Runtime Error just because length squares weren't equal within that 1e-8.

[Michael_Rybak]

1. Totally agree with Destination Goal's post.
2. To add: output of superfluous minus before zero ("-0.0") gets WA, which is bad as well


Here are some test cases that could help.

10 10 10.0000001 10 20 10 20.0000001 10
10 10 10.00000001 10 20 10 20.00000001 10
0 1 1 0 0 -1 -1 0
1 1 -1 -1 2 2 -2 -2
0 0 4 4 4 0 4 0
0 0 1 -1 4 0 1 3
0 0 0 0 1.414 0 -1 1
1 0 0 1 5 0 0 5
1 0 0 -1 5 0 0 -5
1 -1 -1 1 5 -1 -5 1
1 -1 1 1 5 -1 1 5
0 0 -21 1 0 1 -21 2
0 0 0 1 0 1 0 2
0 0 1 0 1 0 2 0
1 2 2 1 1 1 1 1
1 1 1 1 1 2 2 1
10 10 10.0000001 10 20 10 20.0000001 10
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0

My AC output is:

Translation by vector <0.0,0.0>.
No move.
Rotation around (0.0,0.0) by 270.0 degrees counterclockwise.
Rotation around (0.0,0.0) by 180.0 degrees counterclockwise.
Rotation around (4.0,0.0) by 270.0 degrees counterclockwise.
Rotation around (1.0,0.0) by 90.0 degrees counterclockwise.
Rotation around (0.0,0.0) by 135.0 degrees counterclockwise.
Rotation around (0.0,0.0) by 90.0 degrees counterclockwise.
Rotation around (0.0,0.0) by 270.0 degrees counterclockwise.
Rotation around (0.0,0.0) by 180.0 degrees counterclockwise.
Rotation around (0.0,0.0) by 90.0 degrees counterclockwise.
Translation by vector <-21.0,1.0>.
Translation by vector <0.0,1.0>.
Translation by vector <1.0,0.0>.
Rotation around (1.0,1.0) by 270.0 degrees counterclockwise.
Rotation around (1.0,1.0) by 270.0 degrees counterclockwise.
Translation by vector <0.0,0.0>.
Rotation around (0.0,0.0) by 270.0 degrees counterclockwise.


Good luck!

[minskcity]

btw, for all the output, i print the value+1e-9 to avoid rounding error to strange result (e.g. negative zero -0.0)

Thanks . I believe that every problem that has floating point output should explicitly specify that they consider -0.0 wrong answer and have a special correction problem.