10897 - Travelling Distance

All about problems in Volume 108. 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
helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

10897 - Travelling Distance

Post by helloneo »

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..
what's wrong with it.. please help me.. ~
Last edited by helloneo on Tue May 22, 2007 7:55 am, edited 2 times in total.
Top
txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

Post by txandi »

You can simplify your formula:

Code: Select all

dist = acos( sin(rad1) * sin(rad3) +
       cos(rad1) * cos(rad3) * cos(rad2) * cos(rad4) +
       cos(rad1) * cos(rad3) * sin(rad2) * sin(rad4) ) * r;
Top
daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

Nevermind.
Last edited by daveon on Sun Aug 28, 2005 4:24 pm, edited 1 time in total.
Top
helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

thanks..

Post by helloneo »

thanks for help.. ^^
i got AC..
Top
w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k »

Could someboby post some I/O ? I can't find a mistake in my code.

Wojciech
Top
oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

Post by oulongbin »

Could someone tell me how to change the latitude and longitude in this problem?
Top
wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

how to

Post by wook »

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.. :)
Top
oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

Post by oulongbin »

hi wook,thank you very much!
now i get AC :D
Top
w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k »

Could someboby post some I/O ?

Wojciech
Top
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

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
Top
w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k »

Martin,

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

Wojciech
Top
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

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 :)
Top
w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k »

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.
Top
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

w k wrote:Still the same.
Hm... I don't know what might be the problem :oops:

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...
Top
wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

how about

Post by wook »

given latitude,longitude in formular of radian angles,

there is a equation which returns the length of arc(i.e. distance).


if the method above gets WA and WA ....,
(i also hate PRECISION ERROR)

then how about thinking a equation with trigonometric function ?

i think it's not difficult :)
Sorry For My Poor English.. :)
Top
Post Reply

Return to “Volume 108 (10800-10899)”