求めたいものは「星を原点の周りに反時計回りに並べた時、角度の幅が \(180^\circ\) 未満となる連続した星の個数の最大値」です。

（もちろん時計回りでもよいです。また、今回の制約では \(180^\circ\) 丁度はありませんから「以下」としても良いです）

星を原点のまわりに反時計回りに並べる

いわゆる偏角ソートと呼ばれるアルゴリズムです。

簡単な方法として、atan2 などを用いて角度を求め、浮動小数点数で比較することが考えられます。しかし、制約によっては浮動小数点数の誤差が原因で WA となる可能性があります。そこで、今回は整数演算だけで比較する方法を紹介します。

偏角ソートは、外積を用いることで実現できます。（一般には三次元ベクトルに対して定義されますが、ここでは、点 \(a, b\) について \(a \times b = a_x \times b_y - a_y \times b_x\) と定義しましょう）ソートを行うには、任意の二要素の大小を比較できれば十分です。そこで、二つの点 \(a,b\) の偏角を比較する方法を考えましょう。

まず、すべての点の偏角が \([0^\circ,180^\circ)\) の範囲にある場合を考えます。このとき、二つの点の外積 \(a\times b\) を求めれば、次のように比較できます。（二つの点の偏角の差が \(180^\circ\) 未満であれば、外積の符号から偏角の大小を正しく判定できます）

• \(a\times b \gt 0\) ならば、\(a \lt b\)
• \(a\times b=0\) ならば、\(a=b\)
• \(a\times b \lt 0\) ならば、\(a \gt b\)

偏角が \([0^\circ,360^\circ)\) の範囲にある場合、二つの点の偏角の差が \(180^\circ\) を超えることがあるため、外積の符号だけでは正しく比較できません。そこで、点を偏角が \([0^\circ,180^\circ)\) のものと \([180^\circ,360^\circ)\) のものに分けます。

これにより、浮動小数点数を使わずに偏角ソートを実現できます。

角度の幅が \(180^\circ\) 未満となる連続した星の個数の最大値

ソート後であれば、「角度の幅が \(180^\circ\) 未満となる連続した星」は（円環における）区間となっているはずです。

よって、尺取法を考えましょう。点 \(P_l\) を区間の左端とした時、この偏角を \(x\) として「 \([x : x + 180^\circ)\) の区間に点 \(P_r\) の偏角が含まれるかどうか」が判定したいです。制約から丁度 \(x +180^\circ\) が存在しないことに注意すると、これは \(P_l \times P_r \ge 0\) などとして判定することができます。

円環を切り開いて \(2\) 倍の長さにしておくと、簡単に実装できるでしょう。

計算量は \(O(N\log N)\) です。

実装例 (CPython)

from functools import cmp_to_key

def solve():
    n = int(input())
    p = [tuple(map(int, input().split())) for _ in range(n)]

    def cmp(a, b):
        x, y = a
        u, v = b
        h = y < 0 or (y == 0 and x < 0)
        k = v < 0 or (v == 0 and u < 0)
        if h != k:
            return h - k
        z = x * v - y * u
        return (z < 0) - (z > 0)

    p.sort(key=cmp_to_key(cmp))
    p *= 2

    ans = r = 1
    for l in range(n):
        r = max(r, l + 1)
        x, y = p[l]
        while r < l + n:
            u, v = p[r]
            if x * v <= y * u:
                break
            r += 1
        ans = max(ans, r - l)

    print(ans)

for _ in range(int(input())):
    solve()