Game on Plane

Alice and Bob are playing a game. In this game, there are $n$ straight lines on the 2D plane. Alice will select exactly $k$ straight lines $l_1,l_2,\dots,l_k$ among all the $n$ straight lines first, then Bob will draw a straight line $L$. The penalty of Bob is defined as the number of lines in $\{l_1,l_2,\dots,l_k\}$ that shares at least one common point with $L$. Note that two overlapping lines also share common points.

Alice wants to maximize the penalty of Bob while Bob wants to minimize it. You will be given these $n$ lines, please write a program to predict the penalty of Bob for $k=1,2,3,\dots,n$ if both of the players play optimally.

The first line contains a single integer $T$ ($1 \leq T \leq 500$), the number of test cases. For each test case:

The first line contains a single integer $n$ ($1 \leq n \leq 100\,000$), denoting the number of straight lines.

Each of the next $n$ lines contains four integers $xa_i,ya_i,xb_i$ and $yb_i$ ($0\leq xa_i,ya_i,xb_i,yb_i\leq 10^9)$, denoting a straight line passes both $(xa_i,ya_i)$ and $(xb_i,yb_i)$. $(xa_i,ya_i)$ will never be coincided with $(xb_i,yb_i)$.

It is guaranteed that the sum of all $n$ is at most $1\,000\,000$.

For each test case, output $n$ lines, the $i$-th ($1\leq i\leq n$) of which containing an integer, denoting the penalty of Bob when $k=i$.

2
2
1 1 2 2
0 0 2 3
3
1 1 2 2
1 1 2 2
3 2 5 4

0
1
0
0
0

2021“MINIEYE杯”中国大学生算法设计超级联赛（3）