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.
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 space-separated integers - x and y.
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.
- 1 ≤ T ≤ 105
- 1 ≤ N ≤ 105
- 0 ≤ |x|, |y| ≤ 107
- Sum of N over all the test cases in a single test file doesn't exceed 105
- 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.
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
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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|
Fetching successful submissions
If you are still having problems, see a sample solution here.