CF993C.Careful Maneuvering

提高+/省选-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

There are two small spaceship, surrounded by two groups of enemy larger spaceships. The space is a two-dimensional plane, and one group of the enemy spaceships is positioned in such a way that they all have integer yy-coordinates, and their xx-coordinate is equal to −100-100, while the second group is positioned in such a way that they all have integer yy-coordinates, and their xx-coordinate is equal to 100100.

Each spaceship in both groups will simultaneously shoot two laser shots (infinite ray that destroys any spaceship it touches), one towards each of the small spaceships, all at the same time. The small spaceships will be able to avoid all the laser shots, and now want to position themselves at some locations with x=0x=0 (with not necessarily integer yy-coordinates), such that the rays shot at them would destroy as many of the enemy spaceships as possible. Find the largest numbers of spaceships that can be destroyed this way, assuming that the enemy spaceships can't avoid laser shots.

有两艘小型宇宙飞船,被两组较大的敌方宇宙飞船包围。空间是一个二维平面,其中一组敌方宇宙飞船的位置满足:它们的 yy-坐标均为整数,且 xx-坐标均为 −100-100;另一组敌方宇宙飞船的位置满足:它们的 yy-坐标均为整数,且 xx-坐标均为 100100。

这两组中的每艘敌方宇宙飞船将同时发射两条激光束(即无限延伸的射线,任何被其扫过的宇宙飞船均会被摧毁),每条激光束分别射向两艘小型宇宙飞船,且所有激光束在同一时刻发射。两艘小型宇宙飞船能够避开所有激光束,现在希望将自身定位在某处满足 x=0x = 0 的位置上(其 yy-坐标不必为整数),使得射向它们的激光束尽可能多地摧毁敌方宇宙飞船。假设敌方宇宙飞船无法避开激光束,求最多可摧毁的敌方宇宙飞船数量。

输入格式

The first line contains two integers nn and mm (1≤n,m≤601 \le n, m \le 60), the number of enemy spaceships with x=−100x = -100 and the number of enemy spaceships with x=100x = 100, respectively.

The second line contains nn integers y1,1,y1,2,…,y1,ny_{1,1}, y_{1,2}, \ldots, y_{1,n} (∣y1,i∣≤10 000|y_{1,i}| \le 10\,000) — the yy-coordinates of the spaceships in the first group.

The third line contains mm integers y2,1,y2,2,…,y2,my_{2,1}, y_{2,2}, \ldots, y_{2,m} (∣y2,i∣≤10 000|y_{2,i}| \le 10\,000) — the yy-coordinates of the spaceships in the second group.

The yy coordinates are not guaranteed to be unique, even within a group.

第一行包含两个整数 nn 和 mm(1≤n,m≤601 \le n, m \le 60),分别表示位于 x=−100x = -100 处的敌方飞船数量和位于 x=100x = 100 处的敌方飞船数量。

第二行包含 nn 个整数 y1,1,y1,2,…,y1,ny_{1,1}, y_{1,2}, \ldots, y_{1,n}(∣y1,i∣≤10 000|y_{1,i}| \le 10\,000)—— 第一组飞船的 yy 坐标。

第三行包含 mm 个整数 y2,1,y2,2,…,y2,my_{2,1}, y_{2,2}, \ldots, y_{2,m}(∣y2,i∣≤10 000|y_{2,i}| \le 10\,000)—— 第二组飞船的 yy 坐标。

yy 坐标不保证互异,即使在同一组内也可能重复。

输出格式

Print a single integer – the largest number of enemy spaceships that can be destroyed.

输出一个整数——能够摧毁的敌方飞船的最大数量。

输入输出样例

  • 输入#1

    3 9
    1 2 3
    1 2 3 7 8 9 11 12 13

    输出#1

    9
  • 输入#2

    5 5
    1 2 3 4 5
    1 2 3 4 5

    输出#2

    10

说明/提示

In the first example the first spaceship can be positioned at (0,2)(0, 2), and the second – at (0,7)(0, 7). This way all the enemy spaceships in the first group and 66 out of 99 spaceships in the second group will be destroyed.

In the second example the first spaceship can be positioned at (0,3)(0, 3), and the second can be positioned anywhere, it will be sufficient to destroy all the enemy spaceships.

在第一个例子中,第一艘我方飞船可以放置在 (0,2)(0, 2),第二艘放置在 (0,7)(0, 7)。这样可摧毁第一组中的所有敌方飞船,以及第二组中 99 艘敌方飞船中的 66 艘。

在第二个例子中,第一艘我方飞船可以放置在 (0,3)(0, 3),而第二艘可放置于任意位置,即可摧毁所有敌方飞船。

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

首页