Problem 3509 --Photography

3509: Photography

正确率: $0.00\%$ 下一题

Time Limit	$1$ 秒/Second(s)	Memory Limit	$512$ 兆字节/Megabyte(s)
提交总数	$0$	正确数量	$0$
裁判形式	标准裁判/Standard Judge	我的状态	尚未尝试
难度		分类标签

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=1 | P | \sum i\inP \sum j\inP d(i,j) 2 - - - - - - - - - - - \sqrt

where

Pis 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

(1≤T≤10), denoting the number of test cases.
For each test case, the first line consists of only one integer

(1≤n≤106), denoting the number of events. Then follow

nlines, 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

iis 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

nin all test cases is less than

3000000.

Output

For each event in each test case, print the maximum value of

Safter the event happens, within an absolute or relative error of no more than

10−9.

Sample Input复制

Sample Output复制

0
1.4142135624
1.3333333333
1.5811388301
0
1
0.8164965809
0.7071067812
0.8164965809
1

赛题来源/所属竞赛 2020 Multi-University Training Contest 10 N/A

竞赛编号	竞赛名称	竞赛时间	访问比赛

本题记录	用户（点击查看用户）	运行号（点击购买题解）	时间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战