129 - ZOJ Monthly, December 2013 - J
Actually, extraterrestrials had arrived at the earth in 10 thousands years ago, and they monitored the creature on the earth, especially for their process and evolution. They put some monitors on the (xi, yi) (xi is longitude, yi is latitude, and both of them are integers), and then drove UFO to the earth to collect and analysis the data from earth. For some reasons, they can only receive data from monitors whose spherical distance to them is not longer than m kilometers.
Now, they want to know that how many monitors' data could they receive when the UFO at the point(xi, yi), as mentioned above.
There are multiple input cases. For each case, the first line contains two integers n and m, n is the times of operating, m is as mentioned above.Then followed by n lines, each line contains a char op and two integers xi, yi. When op equals 'i', it means put a monitor on (xi, yi). If op equals 'c', you should output the number of monitors that its' data could be received by UFO landing on (xi, yi). You could suppose the earth is a normal sphere, and the radius of the earth is 6378 kilometres. (-180 <= xi < 180, -90 <= yi <= 90, 0 < n <=30000, 0 <= m)
When op equals 'c', you should output one line, it contains a integer, as mentioned above.
3 300 i 0 0 i 0 90 c 1 1
The spherical distance between two points, (x1 , y1) and (x2 , y2), is r*arccos(sin(y1)*sin(y2)+cos(y1)*cos(y2)*cos(x1-x2)), x is longitude, y is latitude and r is radius.
Please note the floating point error!
Author: GU, Xuanzhi