## 10897 - Travelling Distance

Moderator: Board moderators

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### 10897 - Travelling Distance

Code: Select all

``````CUT AFTER AC
``````

first i change latitudes and longitudes to x y z coordinate..
and then i get the angle between 2 positions..
it's all ok for sample inputs.. but WA..
Last edited by helloneo on Tue May 22, 2007 7:55 am, edited 2 times in total.

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

Code: Select all

``````dist = acos( sin(rad1) * sin(rad3) +
``````

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Nevermind.
Last edited by daveon on Sun Aug 28, 2005 4:24 pm, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### thanks..

thanks for help.. ^^
i got AC..

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
Could someboby post some I/O ? I can't find a mistake in my code.

Wojciech

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China
Could someone tell me how to change the latitude and longitude in this problem?

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

### how to

oulongbin wrote:Could someone tell me how to change the latitude and longitude in this problem?
ok,

we are given degree, minute, and second.

thus we have to change them into radian values,

a degree b minute c second is equal to (a + b / 60 + c / 3600) * PI / 180

and, moreover, if direction is 'S' or 'W', we need to make angles negative (i.e multiply -1)

now, there are two ways to calculate the distance :

1) convert radian values to xyz coordinates,
and calculate a line distance, get difference angle,
then we can get the length of arc.

2) use general formula, that is, equation
(with sin, cos functions)
Sorry For My Poor English..

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China
hi wook,thank you very much!
now i get AC

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
Could someboby post some I/O ?

Wojciech

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
w k wrote:Could someboby post some I/O ?
Here you have some random inputs:

Code: Select all

``````100
78 9 19.57 N 135 31 54.90 E 31 6 39.53 N 89 53 45.40 W
71 37 28.5 S 70 34 36.79 W 59 32 11.51 N 74 41 31.21 W
61 36 38.50 N 15 33 0.67 E 19 50 38.69 N 172 57 38.57 W
51 55 55.30 S 45 58 35.94 W 2 46 57.15 S 39 30 31.14 E
5 54 37.0 S 23 14 39.55 E 54 58 6.38 N 65 16 19.53 E
23 23 19.76 S 5 6 36.53 W 85 12 16.42 N 100 37 31.88 E
86 33 44.52 N 43 48 56.13 W 57 39 37.74 S 164 59 23.2 W
6 55 42.15 N 44 21 28.13 E 41 59 55.88 S 42 14 27.68 E
54 18 23.94 S 74 9 20.49 W 22 23 24.60 S 43 31 21.81 W
68 24 23.58 S 119 4 49.2 W 29 22 22.24 S 58 39 44.87 W
78 49 49.20 N 90 30 56.72 W 21 47 54.27 N 40 4 13.16 W
29 15 56.63 N 4 35 24.82 W 87 14 34.8 N 127 5 41.11 W
77 35 0.9 N 68 28 32.10 W 58 32 58.69 S 27 23 19.95 W
34 7 50.28 N 114 13 25.36 W 72 11 42.54 N 110 14 12.35 E
13 49 25.30 N 88 20 30.56 W 11 3 8.13 N 3 20 0.75 W
49 56 34.31 S 9 9 18.87 E 1 38 44.28 N 180 29 46.8 W
59 7 46.22 S 108 31 21.22 E 90 35 54.5 N 92 47 20.32 W
76 58 33.12 S 146 10 11.77 W 29 57 9.8 N 98 8 9.8 W
44 10 36.89 S 95 30 8.59 W 62 7 10.44 N 116 52 31.70 W
38 50 41.56 N 49 50 13.57 E 67 40 46.94 S 2 31 55.90 W
6 23 48.85 N 99 45 34.77 E 61 40 45.6 N 38 36 54.20 W
71 26 16.41 S 155 27 55.1 E 63 47 10.80 N 178 48 53.61 E
34 20 5.95 S 37 16 56.63 E 13 15 52.8 S 128 53 48.59 E
43 3 47.73 N 10 36 34.77 W 2 17 53.11 S 92 17 6.39 W
20 10 36.87 N 159 32 54.96 W 51 48 54.25 N 154 1 38.4 W
66 30 55.53 S 145 24 2.11 E 21 27 15.42 S 174 24 0.90 E
9 56 52.57 N 83 43 21.43 W 84 1 37.40 S 94 3 33.52 E
5 40 10.73 N 165 54 23.82 E 89 41 35.96 N 139 46 59.54 W
47 52 50.72 N 27 57 58.45 E 35 29 33.42 S 52 1 5.43 E
41 51 6.30 N 72 41 18.76 E 53 30 47.16 S 130 23 25.14 W
87 39 5.21 N 16 5 34.77 E 66 50 8.0 S 9 51 19.52 E
11 1 1.39 S 146 7 56.66 W 26 45 30.52 S 72 7 52.65 W
15 11 55.91 S 70 18 5.23 E 73 11 14.12 S 26 12 59.92 E
50 2 4.12 S 121 32 7.95 W 74 37 33.42 S 123 19 29.15 E
38 9 9.61 N 45 33 25.5 E 76 12 22.13 S 125 52 43.72 E
2 59 58.94 S 168 13 38.94 E 24 25 47.68 S 59 36 35.68 W
54 28 39.65 N 29 30 49.64 W 9 4 30.16 N 110 12 2.28 W
53 6 1.48 N 69 55 53.70 W 12 58 23.20 N 43 2 25.45 W
34 44 4.88 N 163 54 52.69 E 71 38 41.13 N 174 12 22.18 W
40 24 37.31 S 16 15 14.97 E 69 26 39.20 S 88 35 6.38 W
36 53 9.12 N 109 35 49.80 W 33 3 56.8 S 145 32 21.85 W
69 32 13.14 S 1 15 22.35 W 17 35 3.7 S 26 35 32.49 E
4 44 36.53 S 132 33 42.90 E 37 40 20.6 N 52 46 57.29 E
26 44 24.64 S 134 8 20.70 E 29 5 51.96 N 19 15 43.26 E
31 37 9.82 N 62 57 11.1 W 50 24 51.77 S 71 35 44.20 E
56 25 57.44 S 115 21 27.26 E 28 28 55.58 N 94 20 8.60 W
56 30 46.61 N 91 36 38.4 E 5 43 15.30 S 130 44 33.33 W
53 33 4.63 S 36 11 44.2 W 31 31 16.30 N 173 31 57.23 W
5 24 1.50 S 92 54 59.41 W 74 30 29.53 N 121 29 49.81 W
72 52 35.54 S 160 45 1.85 E 69 54 19.65 S 155 3 50.83 E
30 37 50.49 S 112 30 40.2 W 28 1 57.94 N 59 35 43.81 E
39 11 3.68 S 159 55 45.76 W 85 37 40.43 S 95 12 54.86 W
18 34 2.37 N 53 35 3.61 E 68 25 4.68 N 127 3 47.70 E
45 39 21.50 N 55 48 53.59 W 63 43 0.65 N 153 26 45.23 W
64 18 38.68 N 106 57 35.96 E 9 13 14.88 S 151 34 39.7 W
59 2 12.35 S 89 41 33.17 E 22 22 32.75 N 83 12 41.52 W
11 19 10.4 N 26 9 25.20 E 12 24 33.31 S 7 56 23.81 W
65 31 49.60 N 145 28 26.28 E 55 57 16.33 N 179 51 45.15 E
66 37 47.43 S 46 16 41.21 W 20 17 29.95 N 164 41 54.51 W
39 14 5.69 S 65 35 54.9 E 21 10 36.19 S 64 45 18.3 E
32 29 26.52 N 4 58 33.4 E 39 9 55.96 S 121 59 51.39 W
51 0 14.2 S 48 41 27.36 W 16 4 45.21 S 139 32 46.68 W
10 59 54.16 S 123 48 37.33 E 6 11 26.64 S 101 25 52.54 E
5 2 57.83 N 156 45 59.41 W 80 43 2.38 N 68 9 54.20 E
80 25 16.6 N 25 56 51.56 E 72 48 37.61 N 128 20 17.47 E
84 44 15.9 S 43 59 25.96 E 87 53 24.90 N 104 24 31.85 W
1 34 14.24 N 134 30 52.42 W 64 32 24.13 N 83 34 58.36 W
40 40 17.11 S 53 48 1.53 W 85 0 53.73 S 8 50 22.61 E
59 0 57.27 S 110 44 59.37 E 43 36 54.12 N 121 51 37.21 E
43 0 35.17 N 26 17 51.78 W 73 32 55.33 N 77 26 3.70 E
87 41 39.45 N 62 49 15.52 E 62 32 53.56 N 97 13 47.67 E
48 23 30.48 S 154 27 23.82 E 75 41 45.54 S 147 5 28.73 E
36 28 23.34 N 94 52 46.71 E 11 53 37.8 N 115 4 25.9 W
31 2 43.26 N 123 59 33.93 W 23 16 45.34 S 17 42 46.68 E
83 11 40.57 S 29 49 51.13 E 73 3 48.67 S 140 1 54.94 E
10 30 59.82 N 86 24 38.34 E 9 23 6.99 N 174 32 47.7 E
13 17 36.12 N 114 32 21.25 W 19 37 40.37 S 76 21 13.84 E
38 19 39.24 N 101 21 7.40 E 67 12 16.30 S 88 16 44.1 W
34 3 30.34 N 49 14 47.86 W 37 59 3.88 S 13 21 47.13 E
18 27 37.37 N 98 29 43.62 W 28 19 24.72 S 150 27 26.20 E
12 20 55.35 N 137 14 20.94 E 76 45 45.25 N 104 22 7.90 W
83 2 36.90 S 53 42 34.50 E 14 48 5.67 N 35 5 45.2 E
81 27 54.72 N 157 38 19.6 W 47 31 22.96 N 138 2 1.87 E
23 9 28.63 N 145 24 5.41 W 50 28 3.66 S 122 12 23.79 E
48 57 46.47 N 153 42 25.5 W 3 6 22.14 S 45 11 56.5 W
80 58 7.85 N 132 47 4.30 E 84 19 53.82 N 49 40 37.8 W
15 27 37.46 N 133 28 17.73 E 36 26 21.15 N 126 30 48.51 E
37 28 1.63 S 152 42 15.91 W 75 35 50.67 S 180 24 32.27 W
43 21 43.3 S 50 29 53.47 W 32 24 12.63 N 98 43 7.69 W
84 13 51.21 N 18 22 16.88 E 18 20 28.42 S 18 23 22.69 E
59 44 33.27 N 117 4 41.3 W 9 44 20.95 N 72 37 9.35 W
27 14 12.54 S 46 10 35.37 W 69 38 39.21 N 152 24 21.27 W
44 11 58.77 N 162 48 20.72 W 22 14 16.62 S 41 9 33.61 E
29 5 45.34 S 109 15 12.68 E 83 34 21.55 N 101 27 51.53 W
84 1 43.69 N 15 57 37.15 W 6 25 58.55 S 82 46 1.60 E
73 27 42.22 N 165 44 9.14 W 48 45 31.89 S 83 43 5.8 E
22 39 12.24 N 81 26 1.53 W 56 3 22.51 N 117 19 24.84 E
64 49 9.21 S 54 36 14.15 W 32 24 55.77 S 167 30 10.21 E
39 24 31.99 S 86 38 59.54 W 64 49 14.44 N 15 26 40.80 E
55 6 6.90 N 1 5 28.23 W 78 59 4.15 S 121 57 5.92 E``````
My AC's output:

Code: Select all

``````7507.87
14587.96
10926.03
9454.52
7798.59
12743.71
16602.98
5444.72
4373.01
5792.41
6826.25
6920.94
15396.94
7705.27
9185.14
14567.42
16520.40
12325.63
11973.30
12626.68
11645.92
15141.31
9326.01
9508.12
3550.57
5416.48
11777.37
9357.23
9574.07
17871.15
17179.61
7881.11
7023.34
5358.52
13859.39
14017.47
8586.39
5055.47
4298.07
6384.55
8625.74
6083.48
9437.06
13695.55
15755.66
16127.56
13261.69
15841.17
9094.56
386.75
19197.48
5455.65
7418.76
5906.85
11482.41
15899.87
4596.52
2112.35
13309.78
2009.59
15245.19
8684.18
2516.81
10178.90
2372.50
19610.71
8095.88
5247.51
11457.70
5867.58
2844.39
3054.84
13788.67
16149.37
2255.81
9616.66
18657.39
16748.07
10289.70
12982.10
9357.77
10919.31
4380.42
12134.89
11610.67
1634.16
2432.34
4468.27
9746.06
11405.52
6667.40
13458.24
16733.21
13850.77
10819.62
15776.08
11085.66
8603.26
14460.48
16661.99``````

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
Martin,

I've exactly the same output as You but I get WA. Are there any specific I/O's?

Wojciech

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
w k wrote:I've exactly the same output as You but I get WA. Are there any specific I/O's?
I do not know about any very specific inputs. I generated a few more test cases for you:

http://www.ksp.sk/~martin/val/10897/in.gz (2.1 M)
http://www.ksp.sk/~martin/val/10897/out.gz (0.3 M)

If doesn't help, try to post you code here

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
Still the same.

Here is my code:
Last edited by w k on Thu Sep 01, 2005 8:11 pm, edited 1 time in total.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
w k wrote:Still the same.
Hm... I don't know what might be the problem

I haven't found any bug in the code... Maybe, some precision error could cause the problem, but if it were so, I think, it would have rised up in some test case we have tried...

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of