Description
Given two vectors A and B, compute the angle between them in degrees (0~180).
You should use the following equation:
where • means dot product, and 
The dot product is the sum of the product of the corresponding components of the two vectors. For example, the dot product of [1,2,3] and [4,5,6] is 32 because 1*4+2*5+3*6 = 32.
After getting the cosine value, you can use arccos to get the angle.
The following is an example of arccos and square root:
#include#include int main() { // square root of 9 printf("%f\n", sqrt(9)); // arccos of 0.5 in degrees printf("%f\n", acos(0.5)*(180/M_PI)); return 0; }
Furthermore, we represent a high-dimensional sparse vector by using the following format:
dim1:value1 dim2:value2 dim3:value3 … dimN:valueN 0:0
where 0:0 denotes the end of the vector.
An example: The vector [0,5,0,0,9,0,0,33] is an eight-dimensional vector, which can be represented as
2:5 5:9 8:33 0:0
That is, we may omit all dimensions whose values are zero. Such a representation is compact and particularly suitable for high-dimensional sparse vectors.
Note that the dimensions may be presented in arbitrary order. For example, the above vector may also be expressed as
8:33 2:5 5:9 0:0
Input
The input has three lines.
The first line is the dimension of the vectors.
The following two lines contain two vectors of integer values represented in the sparse format.
The usage of memory is limited to 32 MB.
The dimension of the vector is no greater than 231-1, and the N of dimN will not exceed 220.
Output
The angle between the two vectors in degrees (0~180) and a newline at the end.
Note that you should do rounding and output the angle as an integer.
The following is an example of rounding:
#include#include int main() { printf("%f", round(29.59)); return 0; }