11509 - Touring Robot

[baodog]

I cannot understand this problem.
1) You have to follow the order of the points? 0->1->2->3 ... ->n-1->0 and facing 1?
2) The sample IO makes no sense to me. In the first example,
you go (0,0) -> (3,0), turn -> (1,0) -> (0,0) turn to face (1,0).
That's 2 turns!

Help is appreaciated to explain the 2 examples. Thanks!

[zhouerjin]

in this problem a turn means 2*pi

[andmej]

I think the problem description is very ambiguous too. Anyway...
The robot must visit all points in order.
The sequence of points is "circular", in the sense that after visiting the last point the robot must visit again the first point.
The robot finishes looking in the same direction that he started. (That's why the answer is always an integer).
What you have to print is the number of 360º rotations that the robot will make. In other words, the total number of degrees "swept" by the robot's line of sight divided by 360 (Or 2*pi).

Some more test cases:

Code: Select all

4
0 0
1 0
1 1
0 1
3
0 0
1 1
2 0
0

Correct output is:

Code: Select all

1
2

[azk84]

My program calculates angle of new direction and subtracts it from angle of previous direction and adds the result to a variable that keeps total degrees that the robot turned, when a new point is read from input. And finally it divides it by 2*pi and rounds it to nearest integer.
I tested it for every test case that I could, and it gives correct answer, but I got WA . I think it's because of floating points. Is there another way that doesn't use floating point operations? Plz help me.

[andmej]

How are you calculating angles? I used atan2 and doubles for the calculations and then print the answer like this (without rounding):

Code: Select all

printf("%.0lf\n", ans/(2*pi));

[azk84]

Thanks andmej, I changed my code to print with your printf and I used atan2 instead of atan (I haven't known that atan2 exists and is so simple, special thanks to you ). But I still get WA. Could you give some more tricky test cases plz?

[andmej]

Try these cases:

Code: Select all

3
-10 -2
4 -6
1 7
9
7 9
2 10
-5 4
0 -3
10 10
-7 7
2 -7
-4 0
4 7
4
-6 2
6 5
-7 4
3 9
5
-4 0
-9 0
1 6
7 4
3 -2
10
7 8
-8 4
9 -9
3 -7
-7 -7
8 -1
7 0
10 9
-2 -3
-3 -2
6
10 0
-10 -10
0 -10
-6 -10
9 -3
-2 -7
7
4 -1
-4 6
-8 -7
9 1
-8 0
-4 -2
6 -9
3
-3 -8
-9 0
-8 4
5
7 2
-7 -2
3 8
1 0
0 0
5
-7 -1
-2 2
-2 1
7 10
-8 6
0

My output:

Code: Select all

1
4
2
3
5
3
3
2
3
2

[omar_elruby]

My program gives right output for the above test cases, however i'm still getting WA :( ...
are there other critical inputs to test my program ??!!!!

waiting for help ...
thanks in advance ...

[red_apricot]

I believe there are test cases with n > 1024, I got AC when I changed my N from 0x400 to (1<<20).