7608: Photography
内存限制：128 MB
时间限制：12 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：0
通过：0
题目描述
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
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=1|P|∑i∈P∑j∈Pd(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.
输入格式
The first line of input contains only one integer T (1≤T≤10), denoting the number of test cases.
For each test case, the first line consists of only one integer n (1≤n≤106), 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|≤106), 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 3000000.
For each test case, the first line consists of only one integer n (1≤n≤106), 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|≤106), 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 3000000.
输出格式
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.
输入样例 复制
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输出样例 复制
0
1.4142135624
1.3333333333
1.5811388301
0
1
0.8164965809
0.7071067812
0.8164965809
1