해결한 사람
0
명
정답률
0.00
%
시간 제한
2000
ms
메모리 제한
245
MB
두 대의 작은 우주선이 두 무리의 더 큰 적 우주선들에 둘러싸여 있다. 우주는 이차원 평면이며, 한 무리의 적 우주선들은 모두 정수 y좌표를 갖고 x좌표가 -100이 되도록 배치되어 있고, 두 번째 무리는 모두 정수 y좌표를 갖고 x좌표가 100이 되도록 배치되어 있다.
두 무리의 각 우주선은 모두 동시에, 작은 우주선 각각을 향해 하나씩 두 발의 레이저(닿는 모든 우주선을 파괴하는 무한한 반직선)를 발사한다. 작은 우주선들은 모든 레이저를 피할 수 있으며, 이제 자신들을 향해 발사된 반직선이 가능한 한 많은 적 우주선을 파괴하도록 x=0인 어떤 위치들에 자신을 배치하려 한다(y좌표는 반드시 정수일 필요가 없다). 적 우주선들은 레이저를 피할 수 없다고 가정할 때, 이 방법으로 파괴할 수 있는 우주선 수의 최댓값을 구한다.
첫째 줄에는 두 정수 n와 m (1 ≤ n, m ≤ 60)가 주어진다. 이는 각각 x = -100인 적 우주선의 수와 x = 100인 적 우주선의 수이다.
둘째 줄에는 n개의 정수 , , …, (|| ≤ 10 000)가 주어진다. 이는 첫 번째 무리에 속한 우주선들의 y좌표이다.
셋째 줄에는 m개의 정수 , , …, (|| ≤ 10 000)가 주어진다. 이는 두 번째 무리에 속한 우주선들의 y좌표이다.
y좌표는 같은 무리 안에서조차 서로 다르다고 보장되지 않는다.
파괴할 수 있는 적 우주선 수의 최댓값을 나타내는 정수 하나를 출력한다.
3 9
1 2 3
1 2 3 7 8 9 11 12 13
9
5 5
1 2 3 4 5
1 2 3 4 5
10
첫 번째 예제에서는 첫 번째 우주선을 (0, 2)에, 두 번째 우주선을 (0, 7)에 배치할 수 있다. 그러면 첫 번째 무리의 모든 적 우주선과 두 번째 무리의 우주선 9대 중 6대가 파괴된다.
두 번째 예제에서는 첫 번째 우주선을 (0, 3)에 배치할 수 있고 두 번째 우주선은 어디에나 배치할 수 있으며, 이것으로 모든 적 우주선을 파괴하기에 충분하다.