Photography
TimeLimit:12000MS MemoryLimit:262144KB
64-bit integer IO format:%I64d
未提交 | 登录后收藏
Problem Description
The annual Multi-University Technology Conference is being held in the China Online Convention \& Exhibition Center. As a photographer, your task today is to take photos of people participating in the grand festivity. To make the photo neat, you should make the people in the photo as uniform as possible.
Formally, the exhibition center can be regarded as a two-dimensional plane, and people can be seen as points in the plane. You may orient your camera in an arbitrary direction, and all points representing the people are projected to a line perpendicular to your orientation. You should maximize
$$S = \frac{1}{|P|} \sqrt{\sum_{i \in P} \sum_{j \in P} d(i,j)^2} $$
where $P$ is the current set of people, $d(i,j)$ is the distance between the projected points of the $i$-th and $j$-th persons on the line.
Since the people are of high mobility, you should report the optimal value after each event. There are two types of events:
1. a person appears at Cartesian coordinates $(x, y)$;
2. the person appearing since the $i$-th event disappears now.
Initially, there is no person in the exhibition center.
Formally, the exhibition center can be regarded as a two-dimensional plane, and people can be seen as points in the plane. You may orient your camera in an arbitrary direction, and all points representing the people are projected to a line perpendicular to your orientation. You should maximize
$$S = \frac{1}{|P|} \sqrt{\sum_{i \in P} \sum_{j \in P} d(i,j)^2} $$
where $P$ is the current set of people, $d(i,j)$ is the distance between the projected points of the $i$-th and $j$-th persons on the line.
Since the people are of high mobility, you should report the optimal value after each event. There are two types of events:
1. a person appears at Cartesian coordinates $(x, y)$;
2. the person appearing since the $i$-th event disappears now.
Initially, there is no person in the exhibition center.
Input
The first line of input contains only one integer $T$ $(1 \leq T \leq 10)$, denoting the number of test cases.
For each test case, the first line consists of only one integer $n$ $(1 \leq n \leq 10^6)$, denoting the number of events. Then follow $n$ lines, each describing an event. For an event of type 1, the line contains three integers $1,x,y$ $(|x|, |y| \leq 10^6)$, where $(x, y)$ is the Cartesian coordinates of the person; for an event of type 2, the line contains only two integers $2,i$, where $i$ is the index of the event since which the person appears.
It is guaranteed that, for each event of type 2, the person does exist at the moment of the event. It is also guaranteed that after each event, there is at least one person in the center. It is possible that multiple persons are located in the same coordinates.
The sum of $n$ in all test cases is less than $3\,000\,000$.
For each test case, the first line consists of only one integer $n$ $(1 \leq n \leq 10^6)$, denoting the number of events. Then follow $n$ lines, each describing an event. For an event of type 1, the line contains three integers $1,x,y$ $(|x|, |y| \leq 10^6)$, where $(x, y)$ is the Cartesian coordinates of the person; for an event of type 2, the line contains only two integers $2,i$, where $i$ is the index of the event since which the person appears.
It is guaranteed that, for each event of type 2, the person does exist at the moment of the event. It is also guaranteed that after each event, there is at least one person in the center. It is possible that multiple persons are located in the same coordinates.
The sum of $n$ in all test cases is less than $3\,000\,000$.
Output
For each event in each test case, print the maximum value of $S$ after the event happens, within an absolute or relative error of no more than $10^{-9}$.
SampleInput
2 4 1 -1 0 1 1 0 1 0 2 2 1 6 1 1 0 1 0 1 1 0 0 2 1 1 1 1 2 2
SampleOutput
0 1.4142135624 1.3333333333 1.5811388301 0 1 0.8164965809 0.7071067812 0.8164965809 1