Brownie Points II
Those lines divide the plane into four quadrants. The quadrant containing points with arbitrarily large positive coordinates is the top-right quadrant.
The players score according to the number of brownie points in the quadrants. If a brownie point is crossed by a line, it doesn’t count. Stan gets a point for each (uncrossed) brownie point in the top-right and bottom-left quadrants. Ollie gets a point for each (uncrossed) brownie point in the top-left and bottom-right quadrants.
Stan and Ollie each try to maximize his own score. When Stan plays, he considers the responses, and chooses a line which maximizes his smallest possible score. If there is more than one line maximizing Stan’s smallest possible score, he picks any one of them.
What is the largest score which Stan can assure for himself? And over the lines maximizing Stan’s smallest possible score, what are the possible maximum scores that Ollie can get?
The first line of input contains a positive odd integer $1 \le n < 200\, 000$ which is the number of brownie points. Each of the following $n$ lines contains two integers, the horizontal ($x$) and vertical ($y$) coordinates of a brownie point. No two brownie points occupy the same place. Coordinates are bounded in absolute value by $10^9$.
Print a line of output in the format shown below. The first number is the largest score which Stan can assure for himself. The remaining numbers are the possible (high) scores of Ollie, in increasing order.
|Sample Input 1||Sample Output 1|
11 3 2 3 3 3 4 3 6 2 -2 1 -3 0 0 -3 -3 -3 -2 -3 -4 3 -7
Stan: 7; Ollie: 2 3;