OJ Board

Posted: **Sat Aug 27, 2005 6:57 pm**

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.. ~

Posted: **Sat Aug 27, 2005 10:52 pm**

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;

Posted: **Sun Aug 28, 2005 12:20 am**

Nevermind.

Posted: **Sun Aug 28, 2005 7:06 am**

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

Posted: **Sun Aug 28, 2005 11:34 am**

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

Wojciech

Posted: **Sun Aug 28, 2005 1:44 pm**

Could someone tell me how to change the latitude and longitude in this problem?

Posted: **Sun Aug 28, 2005 4:14 pm**

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)

Posted: **Tue Aug 30, 2005 5:10 am**

hi wook,thank you very much!
now i get AC

Posted: **Wed Aug 31, 2005 9:21 pm**

Could someboby post some I/O ?

Wojciech

Posted: **Wed Aug 31, 2005 9:35 pm**

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

Posted: **Wed Aug 31, 2005 10:09 pm**

Martin,

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

Wojciech

Posted: **Wed Aug 31, 2005 10:23 pm**

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

Posted: **Wed Aug 31, 2005 10:53 pm**

Still the same.

Here is my code:

Posted: **Thu Sep 01, 2005 7:22 am**

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...

Posted: **Thu Sep 01, 2005 10:09 am**

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

OJ Board

10897 - Travelling Distance

10897 - Travelling Distance

thanks..

how to

how about