CF1041F.Ray in the tube
省选/NOI-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a tube which is reflective inside represented as two non-coinciding, but parallel to Ox lines. Each line has some special integer points — positions of sensors on sides of the tube.
You are going to emit a laser ray in the tube. To do so, you have to choose two integer points A and B on the first and the second line respectively (coordinates can be negative): the point A is responsible for the position of the laser, and the point B — for the direction of the laser ray. The laser ray is a ray starting at A and directed at B which will reflect from the sides of the tube (it doesn't matter if there are any sensors at a reflection point or not). A sensor will only register the ray if the ray hits exactly at the position of the sensor.
Examples of laser rays. Note that image contains two examples. The 3 sensors (denoted by black bold points on the tube sides) will register the blue ray but only 2 will register the red.
Calculate the maximum number of sensors which can register your ray if you choose points A and B on the first and the second lines respectively.
给你一个内部具有反射性的管子,其形状由两条不重合但均平行于 Ox 轴的直线表示。每条直线上都标有一些特殊的整数点——即管子两侧的传感器位置。
你将在该管子中发射一束激光。为此,你需要在第一条直线和第二条直线上分别选择两个整数点 A 和 B(坐标可以为负):点 A 决定激光的发射位置,点 B 决定激光的方向。激光是一条起始于点 A 并指向点 B 的射线,它将在管壁之间反复反射(反射点处是否有传感器不影响反射过程)。仅当激光恰好击中某个传感器所在位置时,该传感器才会记录下这束激光。
激光射线示例。注意图中包含两个示例:蓝色射线会被 3 个传感器(用管壁上加粗的黑点表示)记录,而红色射线仅被其中 2 个传感器记录。
若你在第一条直线和第二条直线上分别选择点 A 和 B,求最多有多少个传感器能够记录下你的激光射线。
输入格式
The first line contains two integers n and y1 (1≤n≤105, 0≤y1≤109) — number of sensors on the first line and its y coordinate.
The second line contains n integers a1,a2,…,an (0≤ai≤109) — x coordinates of the sensors on the first line in the ascending order.
The third line contains two integers m and y2 (1≤m≤105, y1<y2≤109) — number of sensors on the second line and its y coordinate.
The fourth line contains m integers b1,b2,…,bm (0≤bi≤109) — x coordinates of the sensors on the second line in the ascending order.
第一行包含两个整数 n 和 y1(1≤n≤105,0≤y1≤109)—— 第一条直线上传感器的数量及其 y 坐标。
第二行包含 n 个整数 a1,a2,…,an(0≤ai≤109)—— 第一条直线上传感器的 x 坐标,按升序排列。
第三行包含两个整数 m 和 y2(1≤m≤105,y1<y2≤109)—— 第二条直线上传感器的数量及其 y 坐标。
第四行包含 m 个整数 b1,b2,…,bm(0≤bi≤109)—— 第二条直线上传感器的 x 坐标,按升序排列。
输出格式
Print the only integer — the maximum number of sensors which can register the ray.
输出唯一的整数——能够探测到该光线的传感器的最大数量。
输入输出样例
输入#1
3 1 1 5 6 1 3 3
输出#1
3
说明/提示
One of the solutions illustrated on the image by pair A2 and B2.
图中所示的一组解为 A2 和 B2。
输入解题思路,AI测评打分。不知道怎么写?