문제
십자가는 큰 정사각형의 네 꼭짓점과 한 꼭짓점이 겹치는 합동인 작은 네 개의 정사각형이 잘린 도형이다. 아래 그림은 안지름이 I[i]이고 바깥지름이 O[i] (I[i] < O[i])인 십자가를 의미한다.
N개의 십자가 중에서 K개를 적절히 골라 중심이 (0, 0)에 가고 변이 좌표축에 평행하도록 놓을때, K개가 모두 겹치는 영역의 최대 넓이를 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에 N, K가 주어진다. (2 ≤ N ≤ 200,000, 1 ≤ K ≤ N)
두 번째 줄에는 I[i]가 주어진다.
세 번째 줄에는 O[i]가 주어진다. (1 ≤ I[i] < O[i] ≤ 1,000,000,000)
출력
첫 번째 줄에 십자가 K개가 모두 겹치는 영역의 최대 넓이를 출력한다.
예제
5 3
1 2 1 1 2
2 4 3 4 3
5
출처
2019 FunctionCup 3-1번 문제
로그인해야 코드를 작성할 수 있어요.