Misha and Geometry

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Misha is an expert in geometry, so he knows a lot about various geometrical objects. Recently, he learned the definition of a convex polygon and invented too many new problems involving it. Please help him solve one such problem.
You are given N queries, queries can be one of the following two types:
After each query, Misha should find the area of the convex hull of all points which are in the multiset. Initially, multiset of points is empty. Please help him to solve this problem.
Input
The first line of the input contains an integer T denoting the number of test cases. T test cases follow.
For each test case, first line contains an integer N denoting number of queries.
Each of the next N lines contains one character  type of operation, followed by two spaceseparated integers  x and y.
Output
After each query, print the area of the convex hull of points which are in multiset. Your answer should be correct with exactly 1 digit after decimal point.
Constraints
 1 ≤ T ≤ 10^{5}
 1 ≤ N ≤ 10^{5}
 0 ≤ x, y ≤ 10^{7}
 Sum of N over all the test cases in a single test file doesn't exceed 10^{5}
Subtasks
 Subtask #1: (10 pts) Sum of N over all test cases in a single test file will not exceed 100.
 Subtask #2: (20 pts) Sum of N over all test cases in a single test file will not exceed 5000.
 Subtask #3: (70 pts) Original constraints.
Example
Input: 1 6 + 0 0 + 0 4 + 4 0 + 2 2 + 4 4  0 0 Output: 0.0 0.0 8.0 8.0 16.0 8.0
Author:  mgch 
Tester:  iscsi 
Editorial  http://discuss.codechef.com/problems/MGCHGEOM 
Tags  mgch 
Date Added:  6052016 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions