AT_abc481_e.Most Brilliant Starry Sky
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There are N stars on the xy-plane. The i-th star is represented as the point with coordinates (Xi,Yi).
Draw one line that passes through the origin and does not pass through any star, and choose one of the two regions into which the line divides the plane.
Find the maximum possible number of stars contained in the chosen region.
You are given T test cases; solve each of them.
在 xy-平面上有 N 颗星星。第 i 颗星星用坐标为 (Xi,Yi) 的点表示。
画一条经过原点且不经过任何一颗星星的直线,并从该直线将平面划分出的两个区域中任选其一。
求所选区域中可能包含的星星的最大数量。
你将得到 T 组测试数据;请分别求解每组数据。
输入格式
The input is given from Standard Input in the following format:
T
case1
case2
⋮
caseT
Each test case is given in the following format:
N
X1 Y1
X2 Y2
⋮
XN YN
输入从标准输入中按以下格式给出:
T
case1
case2
⋮
caseT
每个测试用例按以下格式给出:
N
X1 Y1
X2 Y2
⋮
XN YN
输出格式
Print T lines. The i-th line should contain the answer for the i-th test case.
输出 T 行。第 i 行应包含第 i 个测试用例的答案。
输入输出样例
输入#1
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
输出#1
3 3 15
说明/提示
Sample 1 Explanation:
In the 1-st test case, if you draw the line y=−x and choose the region containing the 1-st star, that region contains the 1-st, 2-nd, and 3-rd stars. It is impossible to include all 4 stars, so the answer is 3.
In the 2-nd test case, if you draw the line x=0 and choose the region to its right, all stars are contained.
Constraints
- 1≤T≤2×105
- 1≤N≤2×105
- The sum of N over all test cases is at most 2×105.
- −109≤Xi,Yi≤109
- (Xi,Yi)=(0,0)
- (Xi,Yi)=(Xj,Yj) (i=j)
- No two distinct stars are collinear with the origin.
- All input values are integers.
样例 1 解释:
在第 1 个测试用例中,若画出直线 y=−x 并选择包含第 1 颗星的区域,则该区域包含第 1、第 2 和第 3 颗星。不可能同时包含全部 4 颗星,因此答案为 3。
在第 2 个测试用例中,若画出直线 x=0 并选择其右侧的区域,则所有星星均被包含。
约束条件
- 1≤T≤2×105
- 1≤N≤2×105
- 所有测试用例的 N 之和不超过 2×105。
- −109≤Xi,Yi≤109
- (Xi,Yi)=(0,0)
- (Xi,Yi)=(Xj,Yj) (i=j)
- 任意两颗不同的星星与原点不共线。
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?