Chef and Guard Towers

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef holds all his secret recipes inside his house. For this reason, Chef wants to make his house secure. To do so, Chef wants to install guard towers in his house.
Unfortunately, due to high costs, Chef can only activate 3 guard towers each night. Chef considers his house safe if the triangle formed by these 3 guard towers as vertices strictly contains his house. Chef's house is located at (0, 0).
On the i^{th} day, Chef plans to install a guard tower at location (x_{i}, y_{i}). Chef wants to know how effective each installation is. Specifically, after every installation, Chef wants to know the number of subsets of 3 guard towers he can activate so that his house becomes safe. Please help him answer this question!
This is an online problem, so you won't get the next point unless you answer the question first. Don't forget to flush the output after every print statement. Please see the note section for details about how to flush the standard output.!
Input
The first line of input contains a single integer N. The next N lines describe the points.
The i^{th} line contains two integers x_{i} and y_{i} denoting the location of Chef's i^{th} guard tower, (x_{i}, y_{i}).
Output
Output N lines. The i^{th} line must contain a single integer, the answer to Chef's question after the i^{th} installation.
Constraints
 x_{i}, y_{i} ≤ 10^{6}
 The points are distinct.
 (x_{i}, y_{i}) ≠ (0, 0)
Subtasks
 Subtask #1: (11 points) 3 ≤ N ≤ 1000
 Subtask #2: (24 points) 3 ≤ N ≤ 12000
 Subtask #3: (65 points) 3 ≤ N ≤ 400000
Example
Input: 6 2 3 3 2 1 1 3 3 4 1 5 5 Output: 0 0 1 1 2 2
Explanation
 After the first and second installations, there aren't enough guard towers for Chef to choose from.
 After the third and fourth installations, there is one set of guard towers that make Chef's house safe: {(2, 3), (3, 2), (1, 1)}.
 After the fifth and sixth installations, there are two sets of guard towers that make Chef's house safe: {(2, 3), (3, 2), (1, 1)} and {(2, 3), (4, 1), (1, 1)}.
Note
You can flush the standard output in C++ by writing fflush(stdout). In Java, you can do that by System.out.flush(). Please read the documentations of a particular language for more details.
Author:  kevinsogo 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/TRICONT 
Tags  aug16 binarysearch hard kevinsogo sqrtdecomp 
Date Added:  2072016 
Time Limit:  9 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 