813 - Robot

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
jhin
New poster
Posts: 1
Joined: Fri Feb 18, 2005 7:30 pm

813 - Robot

Post by jhin »

Hi, everyone.

I think I solved this problem, but I've got WAs.
Is there anything special in this problem? (I read the problem thoroughly.)
Can it be a precision problem? (I used 'double' type)
Somebody help me. :oops:

In addition, I heard that the test data of ACM 1999 world finals
was opened to the public. Where can I get them? :o

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

Hi,

Have you solved the problem? I am getting WA on this problem, maybe we can compare our output to see what's wrong.

Input:

Code: Select all

1 12.09 -45
2 4.50 15.68 90 45
1 14.65 90
7 0.57 0.46 13.55 4.65 8.16 7.07 7.85 -90 90 90 45 0 45 0
5 14.85 3.17 9.08 3.66 8.14 45 -90 -90 45 45
2 14.17 8.98 0 0
2 7.36 12.51 90 45
7 19.00 13.27 3.30 0.50 5.87 12.77 6.45 0 0 -45 -45 -45 -90 -45
3 10.62 15.31 5.62 45 0 45
10 13.78 0.96 13.15 18.05 14.49 1.97 14.87 14.25 4.21 3.27 90 -45 0 -45 -45 -90 45 90 -90 90
7 18.93 13.47 3.96 14.54 7.48 15.09 4.10 -90 90 45 90 -90 90 -45
8 16.83 12.29 5.01 13.76 13.07 18.58 16.01 14.89 -45 0 90 90 45 0 0 0
1 5.77 45
7 17.31 2.79 17.46 5.35 18.83 2.78 17.92 0 -45 0 0 -45 -45 -90
10 0.48 3.00 14.75 11.74 17.40 9.50 19.71 2.88 16.61 13.22 -45 0 -90 -45 45 45 45 45 0 90
1 2.66 90
3 0.84 1.92 19.98 45 0 45
1 2.44 45
8 7.40 10.12 8.07 19.40 0.27 14.56 3.07 12.94 -90 0 90 -45 0 45 -45 90
4 3.47 17.19 3.42 12.95 90 0 45 0
3 18.23 9.61 7.60 -90 -45 45
6 3.12 3.90 8.53 6.21 11.36 2.70 90 45 -45 -90 45 -90
8 2.18 5.97 15.58 11.04 1.77 6.16 10.26 6.35 -45 45 90 -45 0 -45 0 -90
7 17.42 16.51 9.58 11.23 12.86 13.07 9.84 45 0 90 45 -45 90 0
8 16.77 1.27 12.74 9.07 17.05 17.80 17.90 19.05 -90 45 45 90 -45 -45 -45 -45
1 9.20 -45
3 5.81 10.26 0.77 -45 45 -45
1 6.78 -90
10 19.52 18.01 8.57 18.63 4.25 16.71 3.46 7.15 7.98 12.44 90 90 -90 90 -90 -45 -90 0 90 90
4 12.63 12.75 0.48 13.61 -90 90 90 -45
10 9.98 7.19 13.13 7.89 8.08 5.36 0.43 0.00 10.80 4.90 90 90 45 -45 90 90 45 -45 -90 90
5 13.71 10.86 1.28 6.55 5.14 90 90 -45 45 90
8 7.01 4.72 7.77 13.62 5.18 0.66 5.96 11.85 -45 0 -90 45 45 0 -45 -90
10 11.49 17.85 17.96 9.18 4.83 15.44 7.51 11.05 7.71 13.70 45 90 -90 0 90 -90 0 -45 45 90
6 19.90 12.02 14.37 17.64 19.52 8.81 0 0 -90 -90 90 90
5 3.62 0.44 0.57 8.34 4.54 45 45 -45 45 -45
3 15.42 16.65 19.83 -45 90 0
1 13.12 0
4 17.06 3.37 7.90 1.38 -45 -45 -45 -90
8 14.61 6.13 18.77 6.24 19.83 0.18 12.46 14.51 45 0 -45 45 90 -90 90 0
10 16.06 18.31 11.41 8.04 1.08 10.86 13.63 18.96 4.86 17.22 45 90 45 -90 45 0 90 -90 45 -45
7 18.25 8.06 6.02 11.19 2.78 11.51 10.82 90 90 -90 0 -90 0 90
10 18.33 3.45 0.76 4.46 8.76 19.47 15.89 2.93 6.98 1.35 -90 -45 -45 -90 90 -90 90 45 90 90
3 16.57 8.04 8.86 -45 0 90
8 16.69 8.65 16.47 8.74 3.95 12.25 4.50 1.79 -45 0 90 45 90 0 45 -90
2 15.37 4.74 -45 0
4 5.64 2.88 6.35 0.61 -90 0 -90 45
7 18.69 14.94 6.87 11.54 3.53 8.90 11.41 -45 0 -90 -90 45 -45 90
7 12.79 16.96 9.57 7.06 19.40 5.16 12.53 45 0 90 -45 -90 45 45
8 8.73 7.95 7.37 7.54 10.90 15.84 13.75 18.47 0 0 -90 90 90 90 -90 0
1 0.55 90
8 11.91 10.81 0.80 1.52 19.95 15.63 14.60 13.76 45 90 90 90 90 -45 45 45
6 14.25 13.59 12.35 11.80 16.47 12.22 0 90 -90 0 90 -90
4 9.55 0.89 17.27 13.54 45 -90 45 -45
10 16.45 11.93 13.95 1.50 5.49 16.96 18.84 15.98 9.20 8.93 0 45 0 -45 90 -45 0 -45 -90 90
4 8.33 17.50 3.88 8.20 90 -90 90 0
6 11.43 1.61 0.23 19.03 11.49 3.09 45 0 -90 -90 -90 45
6 18.30 3.64 15.35 0.27 4.75 16.99 -45 -45 90 0 45 -90
10 19.40 3.34 8.08 4.66 15.09 7.84 17.97 7.94 1.90 11.77 -45 90 0 0 90 0 0 90 0 90
9 19.25 15.69 18.61 10.89 2.16 14.25 7.61 8.80 10.77 90 45 -90 0 -90 90 -90 45 90
8 2.63 19.86 12.63 5.29 11.20 6.99 3.16 2.09 0 -90 45 0 -90 -90 -90 -45
5 13.71 13.98 3.37 19.56 6.88 -45 90 -90 45 45
2 15.11 6.79 90 -90
1 9.88 -45
8 15.91 19.59 11.34 4.77 17.29 17.79 4.96 5.20 0 90 -90 45 -45 -90 90 -90
4 5.95 0.29 13.07 14.03 90 -90 0 -45
6 4.06 13.20 7.77 5.27 5.63 13.73 0 0 0 -45 -90 -90
1 5.86 45
2 4.26 16.79 90 -45
2 19.58 2.93 0 -90
10 0.33 18.55 4.45 6.76 7.56 15.26 14.05 3.28 16.39 6.36 -45 90 45 0 -90 90 -45 90 0 45
3 8.66 9.30 11.07 0 45 -90
1 3.97 0
4 14.77 2.14 11.05 1.73 90 -45 90 0
10 12.49 10.36 18.27 15.70 16.21 14.25 4.25 16.43 3.36 9.07 -90 0 0 -45 -45 0 -45 -45 45 0
8 19.06 1.98 18.52 18.91 10.43 4.34 13.92 14.92 -90 90 -90 -90 90 45 -90 0
8 2.45 0.14 5.65 6.17 10.47 5.39 14.39 16.02 -90 45 -45 -90 0 0 -45 -45
8 6.78 14.47 15.92 1.23 6.60 0.34 18.94 10.71 0 45 45 45 -90 -90 45 90
2 7.79 15.33 45 90
10 6.08 19.42 14.30 3.01 4.64 13.90 11.96 16.93 9.47 0.03 90 90 45 90 -90 90 -45 90 0 90
2 2.69 0.09 -90 -45
6 4.50 0.15 11.10 17.62 13.42 7.97 45 -45 0 -45 0 45
3 19.61 12.80 16.43 -90 0 0
2 14.56 17.78 -90 0
7 18.03 10.09 3.55 19.46 14.16 16.61 11.86 90 -90 -90 -45 -45 90 0
7 11.19 9.68 16.58 7.97 7.73 4.97 12.09 45 0 -90 -90 45 -90 -45
6 13.84 2.67 4.60 17.28 15.30 9.73 -45 -90 -90 90 -45 -90
2 18.15 2.92 -45 -45
7 19.16 0.02 6.00 10.19 10.64 13.84 1.59 0 -45 -90 -45 90 45 -90
5 8.73 2.52 4.96 1.73 5.86 45 -45 45 0 -45
2 17.89 13.12 -90 0
5 0.74 14.09 12.02 2.87 12.97 -45 0 -90 45 -90
1 9.07 0
8 19.25 10.87 3.89 1.07 8.46 6.00 14.72 2.33 -45 90 45 90 45 -45 45 -90
10 17.60 18.44 15.94 16.32 1.43 8.84 5.42 5.06 2.73 1.46 45 -45 90 0 45 90 0 90 90 -90
10 15.02 14.73 10.03 3.15 18.57 5.10 19.38 5.94 9.86 18.85 -90 -90 -45 90 -90 0 0 0 0 90
5 9.41 4.94 19.09 6.25 12.53 45 0 -90 -45 -90
9 17.37 9.93 0.18 9.26 4.42 1.93 5.24 4.95 11.90 90 45 90 -45 -45 -90 -90 45 90
5 14.48 1.51 17.92 16.76 17.08 90 90 -90 -90 -45
6 0.28 8.07 4.24 10.28 19.62 6.80 -90 45 -45 -45 90 90
8 19.17 18.96 16.30 6.89 0.00 3.57 18.53 17.48 90.00 0.00 -90.00 0.00 90.00 0.00 45.00 -90.00
9 17.10 17.09 6.51 0.00 11.67 7.17 2.15 19.21 8.18 90.00 -90.00 -45.00 0.00 0.00 90.00 45.00 0.00 -90.00
8 10.98 17.31 7.43 4.69 1.70 9.10 12.26 9.96 45.00 90.00 0.00 90.00 0.00 90.00 0.00 0.00
7 9.69 9.91 0.00 11.34 19.55 0.50 7.21 -90.00 -90.00 0.00 -45.00 90.00 0.00 45.00
8 6.88 0.00 18.82 18.29 16.39 4.20 4.67 6.66 0.00 45.00 -90.00 90.00 45.00 0.00 -90.00 -45.00
8 16.96 12.74 3.60 11.54 7.74 1.20 16.67 10.48 45.00 90.00 -90.00 0.00 -90.00 0.00 -90.00 0.00
8 19.63 7.02 1.70 5.15 1.17 14.24 3.00 7.63 90.00 -90.00 0.00 -90.00 0.00 -45.00 45.00 0.00
9 16.81 4.45 11.41 0.00 13.58 1.00 2.74 15.41 15.67 0.00 90.00 90.00 90.00 90.00 -90.00 45.00 0.00 -90.00
9 19.47 4.32 9.61 13.35 0.00 16.71 8.57 9.18 2.77 90.00 45.00 -90.00 -90.00 -90.00 -45.00 -45.00 0.00 -90.00
9 18.66 1.07 0.00 6.53 11.36 11.98 6.03 12.34 18.23 90.00 90.00 90.00 -45.00 0.00 90.00 45.00 -45.00 -45.00
-2
My output:

Code: Select all

Case 1: robot's hand is at (-8.549,0.000,8.549)
Case 2: robot's hand is at (15.587,-11.087,0.000)
Case 3: robot's hand is at (14.650,0.000,0.000)
Case 4: robot's hand is at (23.408,-0.460,22.608)
Case 5: robot's hand is at (4.080,8.926,26.337)
Case 6: robot's hand is at (0.000,0.000,23.150)
Case 7: robot's hand is at (16.206,-8.846,0.000)
Case 8: robot's hand is at (0.404,13.263,21.435)
Case 9: robot's hand is at (23.955,0.000,18.335)
Case 10: robot's hand is at (10.608,52.045,16.627)
Case 11: servo 5 attempts to move arm below floor
Case 12: servo 8 attempts to move arm below floor
Case 13: robot's hand is at (4.080,0.000,4.080)
Case 14: robot's hand is at (-27.376,20.930,35.460)
Case 15: servo 3 attempts to move arm below floor
Case 16: robot's hand is at (2.660,0.000,0.000)
Case 17: robot's hand is at (21.932,0.000,1.952)
Case 18: robot's hand is at (1.725,0.000,1.725)
Case 19: robot's hand is at (-19.691,0.969,38.710)
Case 20: servo 3 attempts to move arm below floor
Case 21: robot's hand is at (-28.825,10.595,5.374)
Case 22: servo 6 attempts to move arm below floor
Case 23: robot's hand is at (-4.334,13.794,30.197)
Case 24: robot's hand is at (35.903,-30.571,24.941)
Case 25: servo 7 attempts to move arm below floor
Case 26: robot's hand is at (-6.505,0.000,6.505)
Case 27: robot's hand is at (-9.896,-7.640,9.126)
Case 28: robot's hand is at (-6.780,0.000,0.000)
Case 29: robot's hand is at (11.500,12.495,17.232)
Case 30: robot's hand is at (-22.254,-12.750,10.104)
Case 31: servo 3 attempts to move arm below floor
Case 32: robot's hand is at (9.078,-18.675,0.546)
Case 33: servo 4 attempts to move arm below floor
Case 34: robot's hand is at (24.118,-20.699,54.790)
Case 35: robot's hand is at (-23.180,17.640,51.440)
Case 36: robot's hand is at (-5.324,-8.850,6.624)
Case 37: robot's hand is at (-10.904,-36.480,10.904)
Case 38: robot's hand is at (0.000,0.000,13.120)
Case 39: robot's hand is at (-19.801,7.309,11.901)
Case 40: robot's hand is at (34.495,14.786,18.904)
Case 41: robot's hand is at (6.939,-3.780,25.583)
Case 42: robot's hand is at (18.250,6.230,28.030)
Case 43: servo 3 attempts to move arm below floor
Case 44: robot's hand is at (-11.137,0.000,23.667)
Case 45: robot's hand is at (11.107,-2.664,19.533)
Case 46: robot's hand is at (-14.220,0.000,14.220)
Case 47: servo 3 attempts to move arm below floor
Case 48: robot's hand is at (-34.804,10.418,33.989)
Case 49: robot's hand is at (61.448,4.247,22.080)
Case 50: robot's hand is at (8.470,-39.760,27.580)
Case 51: robot's hand is at (0.550,0.000,0.000)
Case 52: servo 6 attempts to move arm below floor
Case 53: robot's hand is at (-24.150,-30.060,26.470)
Case 54: servo 3 attempts to move arm below floor
Case 55: robot's hand is at (39.734,22.994,45.450)
Case 56: servo 3 attempts to move arm below floor
Case 57: robot's hand is at (-2.157,19.030,1.259)
Case 58: robot's hand is at (8.834,12.213,18.006)
Case 59: robot's hand is at (13.838,-16.080,27.358)
Case 60: robot's hand is at (15.525,-31.659,15.667)
Case 61: servo 6 attempts to move arm below floor
Case 62: servo 4 attempts to move arm below floor
Case 63: robot's hand is at (15.110,6.790,0.000)
Case 64: robot's hand is at (-6.986,0.000,6.986)
Case 65: robot's hand is at (-35.817,-14.548,16.592)
Case 66: robot's hand is at (-3.971,23.281,-0.000)
Case 67: robot's hand is at (-5.630,13.435,19.048)
Case 68: robot's hand is at (4.144,0.000,4.144)
Case 69: robot's hand is at (16.132,11.872,0.000)
Case 70: robot's hand is at (0.000,2.930,19.580)
Case 71: servo 6 attempts to move arm below floor
Case 72: robot's hand is at (-11.070,-6.576,15.236)
Case 73: robot's hand is at (0.000,0.000,3.970)
Case 74: servo 3 attempts to move arm below floor
Case 75: servo 5 attempts to move arm below floor
Case 76: servo 3 attempts to move arm below floor
Case 77: servo 3 attempts to move arm below floor
Case 78: robot's hand is at (13.195,-37.317,43.207)
Case 79: robot's hand is at (5.508,-15.330,5.508)
Case 80: servo 3 attempts to move arm below floor
Case 81: robot's hand is at (-2.754,0.064,0.000)
Case 82: robot's hand is at (12.792,44.631,12.792)
Case 83: robot's hand is at (-48.840,0.000,0.000)
Case 84: robot's hand is at (-32.340,0.000,0.000)
Case 85: robot's hand is at (17.321,0.077,44.522)
Case 86: robot's hand is at (12.183,19.481,16.512)
Case 87: robot's hand is at (-39.788,-8.149,19.522)
Case 88: robot's hand is at (-14.294,2.065,14.294)
Case 89: robot's hand is at (-21.250,15.455,32.621)
Case 90: robot's hand is at (16.073,9.271,9.383)
Case 91: robot's hand is at (-31.010,0.000,0.000)
Case 92: servo 5 attempts to move arm below floor
Case 93: robot's hand is at (0.000,0.000,9.070)
Case 94: robot's hand is at (9.909,-8.578,27.613)
Case 95: servo 4 attempts to move arm below floor
Case 96: servo 3 attempts to move arm below floor
Case 97: robot's hand is at (-15.337,4.419,17.911)
Case 98: servo 3 attempts to move arm below floor
Case 99: robot's hand is at (43.317,10.567,17.920)
Case 100: servo 3 attempts to move arm below floor
Case 101: servo 6 causes link collision
Case 102: servo 5 causes link collision
Case 103: servo 8 causes link collision
Case 104: servo 4 causes link collision
Case 105: servo 3 causes link collision
Case 106: servo 7 causes link collision
Case 107: servo 6 causes link collision
Case 108: servo 5 causes link collision
Case 109: servo 6 causes link collision
Case 110: servo 4 causes link collision
By the way, it seems that the problem doesn't state clearly, if both collision and move below floor happen, which error message should be printed....
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

avm
New poster
Posts: 33
Joined: Sat Aug 20, 2005 9:59 pm
Location: St. Petersburg

Post by avm »

My WA program gives same output as yours except Case 66.
I thought printing -0.000 is not good idea if judge hasn't checker program.
Also I check with assert that
1) Judge input contains cases with length < 0.001
2) fabs(Angles) <= 91.0 < 180
3) There is no distance between two links which equal 0.001 units
(or there is a bug in my program)

Anybody who accepts subject can give answers for two last cases?

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

.. wrote: By the way, it seems that the problem doesn't state clearly, if both collision and move below floor happen, which error message should be printed....
I don't think there are cases in the judge input where this should matter. I have two versions of my program and both get accepted. They differ in their output for your input, though.
avm wrote: I thought printing -0.000 is not good idea if judge hasn't checker program.
Also I check with assert that
1) Judge input contains cases with length < 0.001
2) fabs(Angles) <= 91.0 < 180
3) There is no distance between two links which equal 0.001 units
(or there is a bug in my program)
I also avoid printing -0.000
(1) Yes, and the way .. treats them is wrong
(2) I don't understand what you mean
(3) I don't know

Happy hunting,
-little joey

avm
New poster
Posts: 33
Joined: Sat Aug 20, 2005 9:59 pm
Location: St. Petersburg

Post by avm »

After changing a bit checking intersection code I get AC.
(Skiping link pairs with same servos positions).

AC output:

Code: Select all

Case 101: robot's hand is at (54.803,17.480,10.087)
Case 102: robot's hand is at (45.158,36.535,6.265)
Case 104: robot's hand is at (-5.276,14.324,25.148)
Case 105: servo 4 attempts to move arm below floor
Case 108: robot's hand is at (36.324,9.130,18.564)
Case 109: servo 6 attempts to move arm below floor
Case 110: servo 4 attempts to move arm below floor

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

Thanks avm.
I was busy since your last reply.
Now have time to find the bug based on your output, thanks a lot :)
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Post Reply

Return to “Volume 8 (800-899)”