2015
07-16

# Polaris of Pandora

Polaris is a star. It is the most magnificent scene in the sky, and the most important navigation star of planet Pandora[1]. People live in Pandora call themselves as "Na’vi"[2], and they all love to fly in the sky with their ikran[3]. When they are flying in the sky, they use Polaris to navigate. Polaris could be used to navigate because that it is always staying in the straight line linking the North Pole and the South Pole of Pandora. That straight line could also be called as "axis of Pandora", and Polaris stays on the North Pole side.
Polaris is too far away from Pandora, so in every place near Pandora, light from Polaris could be regarded as parallel to axis of Pandora. Now several Na’vi ikran riders are flying in the sky of Pandora, they want to know the percentage of their whole flying distance that Polaris is visible. Polaris’s light is quite bright, so Polaris is visible even when it is just on the skyline.
To simplify the problem, Na’vi riders assume that Pandora is a perfect sphere, which have an R radius. A rider starts flying from a point on the Pandora’s surface and lands at another point, the flying height is given as H. Ikran is so powerful that flying time between the surface of Pandora and the flying height could be ignored, and ikran will always fly straight up and down between surface and flying height. Both the starting point and the landing point could be described using latitude and longitude [4] of Pandora. And riders will always choose the shortest path to fly.

There are several test cases. Process to the end of file.
The only line of each test case contains 6 real numbers R (1000 ≤ R ≤ 10000), H (1 ≤ H ≤ R), lat0 (-π/2 < lat0 < π/2), lng0 (-π < lng0 < π), lat1 (-π/2 < lat1 < π/2), lng1 (-π < lng1 < π). R is radius of planet Pandora, H is Na’vi ikran rider’s flying height, lat0 and lng0 are latitude and longitude of starting point, lat1 and lng1 are latitude and longitude of landing point.
We guarantee that starting point and landing point will not be the same, and they also will not be "opposite" (Starting point, landing point and Pandora’s center will not be in the same line.)

There are several test cases. Process to the end of file.
The only line of each test case contains 6 real numbers R (1000 ≤ R ≤ 10000), H (1 ≤ H ≤ R), lat0 (-π/2 < lat0 < π/2), lng0 (-π < lng0 < π), lat1 (-π/2 < lat1 < π/2), lng1 (-π < lng1 < π). R is radius of planet Pandora, H is Na’vi ikran rider’s flying height, lat0 and lng0 are latitude and longitude of starting point, lat1 and lng1 are latitude and longitude of landing point.
We guarantee that starting point and landing point will not be the same, and they also will not be "opposite" (Starting point, landing point and Pandora’s center will not be in the same line.)

1000 10 0 0 0 0.5
4000 1000 0 0.618 1.0 0.618

100.000
64.350
Hint
Reference
[1] Pandora is the fifth moon of the gas giant Polyphemus (both are figures in Greek mythology), which orbits the closest star to the sun, Alpha
Centauri A.
[2] The Na'vi (English: The People) are a race of sentient extraterrestrial humanoids who inhabit the lush jungle moon of Pandora.
[3] Ikran (English: Mountain banshees) are large, bird-like aerial predators that are native to Pandora. They are used by the Na'vi for hunting from the
air and traveling larger distances.
[4] To define latitude and longitude of Pandora, we need to know equator of the planet. The equator is the intersection of Pandora's surface with the
plane perpendicular to axis of Pandora and containing the planet's center. Latitude is a geographic coordinate that specifies the north-south position of a point on the
Pandora's surface, it is the angle between the equator and the line connected point on the surface with the planet's center. Latitude is an angle which ranges from -π/2
at the North pole to π/2 at the South pole. Longitude is a geographic coordinate that specifies the east-west position of a point on the Earth's surface. Points with the
same longitude lie in lines running from the North Pole to the South Pole. The longitude of a point on the surface is measured as an angle east or west from the
Hometree [5], ranging from 0 at the Hometree to π eastward and -π westward. Specifically, it is the angle between a plane
containing the Hometree and a plane containing the North Pole, South Pole and the point on the surface.
[5] Hometrees (Na'vi name: Kelutral) are massive trees that can be found throughout Pandora. Many Na'vi clans make these enormous plants their
home.


# Coder

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2547    Accepted Submission(s): 1013

Problem Description

In mathematics and computer science, an algorithm describes a set of
procedures or instructions that define a procedure. The term has become
increasing popular since the advent of cheap and reliable computers.
Many companies now employ a single coder to write an algorithm that will
replace many other employees. An added benefit to the employer is that
the coder will also become redundant once their work is done. 1

You are now the signle coder, and have been assigned a new task writing
code, since your boss would like to replace many other employees (and
Your code should be able to complete a task to replace these employees who do nothing all day but eating: make the digest sum.

By saying “digest sum” we study some properties of data. For the sake
of simplicity, our data is a set of integers. Your code should give
response to following operations:
2. del x – remove the element x from the set;
3. sum – find the digest sum of the set. The digest sum should be understood by

where the set S is written as {a1, a2, … , ak} satisfying a1 < a2 < a3 < … < ak
Can you complete this task (and be then fired)?
——————————————————————————
1 See http://uncyclopedia.wikia.com/wiki/Algorithm

Input
There’re several test cases.
In each test case, the first line contains one integer N ( 1 <= N <= 105 ), the number of operations to process.
Then following is n lines, each one containing one of three operations: “add x” or “del x” or “sum”.
You may assume that 1 <= x <= 109.
Please see the sample for detailed format.
For any “add x” it is guaranteed that x is not currently in the set just before this operation.
For any “del x” it is guaranteed that x must currently be in the set just before this operation.
Please process until EOF (End Of File).

Output

For each operation “sum” please print one line containing exactly one
integer denoting the digest sum of the current set. Print 0 if the set
is empty.

Sample Input
9
sum
del 3
sum
6
sum

Sample Output
3
4
5

sum[1] = Lsum[1] + Rsum[3],
sum[2] = Lsum[2] + Rsum[4],
sum[3] = Lsum[3] + Rsum[0],
sum[4] = Lsum[4] + Rsum[1];

 #include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <vector>
#include <queue>
#define N 100005
#define llt long long int
using namespace std;

int num[N << 2];//记录区间的个数
llt segtree[N << 2][5];//
struct node
{
int x;
char s[4];
}a[N];
int b[N];
map<int, int> mp;//使用map离散化
void build(int l, int r, int p)
{
memset(segtree[p], 0, sizeof(segtree[p]));
num[p] = 0;
if (l < r)
{
int mid = (l + r) >> 1, pp = p << 1;
build(l, mid, pp);
build(mid + 1, r, pp + 1);
}
}
void update(int l, int r, int p, int pos, int v)
{
if (pos == l && pos == r)
{
segtree[p][0] += 1ll * v;
num[p] = v > 0 ? 1 : 0;
return;
}
int mid = (l + r) >> 1, pp = p << 1;
if (mid >= pos)
update(l, mid, pp, pos, v);
else
update(mid + 1, r, pp + 1, pos, v);
for (int i = 0; i < 5; i++)
segtree[p][i] = segtree[pp][i] + segtree[pp + 1][((i - num[pp]) % 5 + 5) % 5];
num[p] = num[pp] + num[pp + 1];
}
int main()
{
int n, i, k;
while (~scanf("%d", &n))
{
k = 1;
mp.clear();
for (i = 1; i <= n; i++)
{
scanf("%s", a[i].s);
if (a[i].s[0] == 'a')
{
scanf("%d", &a[i].x);
b[k++] = a[i].x;
}
else
if (a[i].s[0] == 'd')
{
scanf("%d", &a[i].x);
a[i].x = -a[i].x;
}
}
build(1, k - 1, 1);
sort(b + 1, b + k);
for (i = 1; i < k; i++)
mp[b[i]] = i;//重新编号
for (i = 1; i <= n; i++)
{
if (a[i].s[0] == 's')
printf("%I64d\n", segtree[1][2]);
else
update(1, k - 1, 1, mp[abs(a[i].x)], a[i].x);
}
}
return 0;
}