AT_abc481_e.Most Brilliant Starry Sky

普及+/提高

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There are NN stars on the xyxy-plane. The ii-th star is represented as the point with coordinates (Xi,Yi)(X_i,Y_i).

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 TT test cases; solve each of them.

在 xyxy-平面上有 NN 颗星星。第 ii 颗星星用坐标为 (Xi,Yi)(X_i,Y_i) 的点表示。

画一条经过原点且不经过任何一颗星星的直线,并从该直线将平面划分出的两个区域中任选其一。

求所选区域中可能包含的星星的最大数量。

你将得到 TT 组测试数据;请分别求解每组数据。

输入格式

The input is given from Standard Input in the following format:

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

Each test case is given in the following format:

NN
X1X_1 Y1Y_1
X2X_2 Y2Y_2
⋮\vdots
XNX_N YNY_N

输入从标准输入中按以下格式给出:

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

每个测试用例按以下格式给出:

NN
X1X_1 Y1Y_1
X2X_2 Y2Y_2
⋮\vdots
XNX_N YNY_N

输出格式

Print TT lines. The ii-th line should contain the answer for the ii-th test case.

输出 TT 行。第 ii 行应包含第 ii 个测试用例的答案。

输入输出样例

  • 输入#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 11-st test case, if you draw the line y=−xy=-x and choose the region containing the 11-st star, that region contains the 11-st, 22-nd, and 33-rd stars. It is impossible to include all 44 stars, so the answer is 33.

In the 22-nd test case, if you draw the line x=0x=0 and choose the region to its right, all stars are contained.

Constraints

  • 1≤T≤2×1051 \le T \le 2 \times 10^5
  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • The sum of NN over all test cases is at most 2×1052 \times 10^5.
  • −109≤Xi,Yi≤109-10^9 \le X_i,Y_i \le 10^9
  • (Xi,Yi)≠(0,0)(X_i,Y_i) \ne (0,0)
  • (Xi,Yi)≠(Xj,Yj) (i≠j)(X_i,Y_i) \ne (X_j, Y_j) ~ (i \ne j)
  • No two distinct stars are collinear with the origin.
  • All input values are integers.

样例 1 解释:
在第 11 个测试用例中,若画出直线 y=−xy=-x 并选择包含第 11 颗星的区域,则该区域包含第 11、第 22 和第 33 颗星。不可能同时包含全部 44 颗星,因此答案为 33。

在第 22 个测试用例中,若画出直线 x=0x=0 并选择其右侧的区域,则所有星星均被包含。

约束条件

  • 1≤T≤2×1051 \le T \le 2 \times 10^5
  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 所有测试用例的 NN 之和不超过 2×1052 \times 10^5。
  • −109≤Xi,Yi≤109-10^9 \le X_i,Y_i \le 10^9
  • (Xi,Yi)≠(0,0)(X_i,Y_i) \ne (0,0)
  • (Xi,Yi)≠(Xj,Yj) (i≠j)(X_i,Y_i) \ne (X_j, Y_j) ~ (i \ne j)
  • 任意两颗不同的星星与原点不共线。
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页