最璀璨的星空

题目描述

平面上有 $N$ 颗星星，第 $i$ 颗星星位于坐标 $(X_i,Y_i)$。

画一条经过原点、且不经过任何星星的直线，并选择这条直线把平面分成的两个区域中的一个。

求被选中的区域内最多能包含多少颗星星。

给定 $T$ 组测试数据，请对每组分别求解。

输入格式

第一行一个整数 $T$。

接下来依次给出 $T$ 组测试数据，每组格式如下：

第一行一个整数 $N$。

接下来 $N$ 行，每行两个整数 $X_i, Y_i$。

输出格式

输出 $T$ 行，第 $i$ 行表示第 $i$ 组测试数据的答案。

3
4
2 1
2 -1
-1 2
-2 -3
3
1 0
2 1
3 -2
20
351656128 486890400
43833334 189818465
244758369 410609525
82390518 959687989
37964139 450230904
-27725133 788196612
392638907 -544184247
-305242056 -60014958
-928747557 460755669
-415081310 638281062
307908966 -865172261
580339611 459847409
42654321 -744472144
-286500328 34461456
-874976232 -245368444
462187336 508372206
-229275227 74979882
-180126519 740406850
877877433 -211582842
256315745 -928285605

3
3
15

数据范围

对于所有测试数据，保证：

• $1\le T\le 2\times 10^5$；
• $1\le N\le 2\times 10^5$，且所有测试数据的 $N$ 之和不超过 $2\times 10^5$；
• $-10^9\le X_i,Y_i\le 10^9$；
• $(X_i,Y_i)\neq(0,0)$；
• 若 $i\neq j$，则 $(X_i,Y_i)\neq(X_j,Y_j)$；
• 任意两颗不同的星星都不与原点共线。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。