Python をお使いの皆様におかれましては、偏角ソートのために比較関数を用意するのは少々面倒に感じられることもあるかと存じます。今回は Python の多倍長整数に頼って、この部分をさぼらせていただきます。

数え上げの考え方は、sounansya さんの解説で紹介されている snuke さんの解法と同じです。以下では、点とその反対向きの仮想的な点を同じ傾きとして扱い、半周分だけ処理します。ここでは、そのソートを Python で簡単に書く方法を説明します。

\(x\ne 0\) の点 \((x,y)\) に対して、傾き \(y/x\) をそのまま計算する代わりに、次の整数を使います。

(y << 60) // x

十分に大きくしてから整数除算することで、傾きの順序を保った整数のキーが得られます。Python の整数には固定幅の桁あふれがありませんので、あとは普通に sort するだけです。浮動小数点数や、外積を使った比較関数は必要ありません。

今回の制約では、\(60\) ビット左にシフトすれば十分なことを確認しておきます。異なる傾きの差は、

\[ \left|\frac{y_1}{x_1}-\frac{y_2}{x_2}\right| =\frac{|y_1x_2-y_2x_1|}{|x_1x_2|} \ge\frac{1}{10^{18}} \]

です。分子は \(0\) でない整数で、分母は高々 \(10^{18}\) だからです。\(2^{60}>10^{18}\) なので、シフト後の差は \(1\) より大きく、切り捨てても順序は変わりません。

必要なビット数の見積もりが面倒でしたら、<<99 や <<100 としておいてもよいでしょう。今回の座標の範囲では十分です。Python ですので、このくらいは大きな整数にお任せできます。何と言っても Python ですのでね。

残る \(x=0\) は、そのままでは割り算ができません。今回は相異なる \(2\) 点と原点が同一直線上にないので、次のように少し方向をずらしておきます。

if x == 0:
    x = 1
    y <<= 60

元の非垂直な点の傾きは絶対値が \(10^9\) 以下ですが、置換後の傾きの絶対値は \(2^{60}\) 以上です。垂直な点は高々 \(1\) 個なので、他の点の方向やその反対方向を追い越さずにずらせます。角度そのものは変わりますが、直線を回したときに点を通過する順序と答えは変わりません。

なお、\(x=0\) の場合は \(y\) を合計 \(120\) ビットもシフトすることになり、やたらと大きな整数になってしまいますが、Python ですので問題ないでしょう。

実装では、最初に \(x<0\) の点数を \(c\) とし、傾きの昇順に \(x>0\) なら \(c\) を \(1\) 増やし、\(x<0\) なら \(1\) 減らします。初期状態と各更新後の \(\max(c,N-c)\) の最大値が答えです。点の上ではなく、隣り合う傾きの間を調べています。

時間計算量は各テストケースにつき \(\mathrm{O}(N\log N)\)、空間計算量は \(\mathrm{O}(N)\) です。座標の上限は定数として扱っています。

実装例 (Python)

for _ in range(int(input())):
    n = int(input())
    events = []
    count = 0
    for _ in range(n):
        x, y = map(int, input().split())
        if x == 0:
            x = 1
            y <<= 60
        negative = x < 0
        count += negative
        events.append(((y << 60) // x, 1 - 2 * negative))
    events.sort()
    answer = max(count, n - count)
    for _, change in events:
        count += change
        answer = max(answer, count, n - count)
    print(answer)

補足：同一直線上に点がある場合

先ほどは「同一直線上にないので」として少々さぼりましたが、その条件がなくても対応できます。原点を含まず、座標の範囲が同じ場合を考えます。

\(x\ne 0\) のとき、点を非零の倍率 \(k\) で拡大・縮小しても、

\[ \left\lfloor\frac{(ky)2^{60}}{kx}\right\rfloor =\left\lfloor\frac{y2^{60}}{x}\right\rfloor \]

ですので、キーは変わりません。\(k<0\) の場合も同じです。したがって、原点と同一直線上にある非垂直な点は、反対向きの場合も同じキーにまとまります。

\(x=0\) の処理を次のように変えます。

if x == 0:
    sign = 1 if y > 0 else -1
    x = sign
    y = sign << 60

これなら上向きは \((1,2^{60})\)、下向きは \((-1,-2^{60})\) となり、反対向きの関係を保ったままずらせます。どちらも傾きは \(2^{60}\) なので、同じキーになります。同じ向きの垂直な点が複数あっても、すべて同じ向きにまとまります。

また、同じ傾きの点は直線が同時に通過するため、まとめて更新する必要があります。上の実装の最後のループを、itertools.groupby を使って次のように置き換えればよいです（先頭に from itertools import groupby を追加します）。

for _, group in groupby(events, key=lambda event: event[0]):
    count += sum(change for _, change in group)
    answer = max(answer, count, n - count)

同じ傾きの途中で答えを更新しないことが大切です。例えば上向きと下向きの点が \(1\) 個ずつある場合、片側に入るのは \(1\) 個ですが、片方だけを更新した途中の状態を数えると \(2\) 個と数えてしまうことがあります。

このように、先ほどさぼらせていただいた部分もほんの少しの書き換えで対応できます。Python をお使いの皆様、偏角ソートは怖くありません。