힘의 장
면접 대비시간 제한1초메모리 제한512 MB
원점을 한 꼭짓점으로 하는 축에 평행한 직사각형 n개 중 정확히 k개를 골라 공통 교집합의 넓이가 최대가 되도록 하고, 그 넓이를 출력한다.
문제
물리생물학 실험실에서는 힘의 장을 통과한 방사선이 식물에 미치는 영향을 연구한다.
실험 장치는 가로 10^9 × 10^9 크기의 정사각형 플랫폼으로, 비옥한 흙으로 채워져 있다. 플랫폼 위에는 방사선원이 설치되어 있다. 방사선원과 플랫폼 사이에는 n개의 힘의 장을 켤 수 있다.
힘의 장 발생기는 점 (0, 0) 위에 설치되어 있다. i번째 힘의 장은 플랫폼의 경계에 평행한 변을 가진 직사각형이며, 서로 마주 보는 두 꼭짓점의 좌표가 (0, 0)과 (x_i, y_i)이다.
실험에서는 k개의 힘의 장을 통과한 방사선이 식물에 미치는 영향을 연구할 계획이다. 주어진 n개의 장 가운데 k개를 실험에 사용할 장으로 골라야 한다. 과학자들은 선택한 k개의 장이 모두 겹치는 플랫폼 영역의 넓이가 최대가 되도록 장을 고르려고 한다.
정수 n, k와 n개의 힘의 장에 대한 설명이 주어질 때, 선택한 k개의 장이 모두 덮는 영역의 넓이가 최대가 되도록 실험에 사용할 k개의 장을 정하고 그 넓이를 출력하는 프로그램을 작성하라.
입력
첫째 줄에는 정수 n과 k가 주어진다(1 ≤ k ≤ n ≤ 200,000). n은 힘의 장의 총 개수이고 k는 실험에 사용할 힘의 장의 개수이다.
다음 n개 줄에는 정수 x_i, y_i가 두 개씩 주어진다(1 ≤ x_i, y_i ≤ 10^9). 이는 i번째 힘의 장인 직사각형에서 원점에서 더 먼 꼭짓점의 좌표이다.
출력
선택한 영역의 최대 넓이를 나타내는 정수 하나를 출력한다.
힌트
그림 1은 입력 파일에 주어진 다섯 개의 힘의 장을 나타낸다. 이 가운데 세 개를 실험에 사용할 장으로 고르는 최적의 방법은 그림 2에 나와 있다.
그림 1. 입력 데이터 예시에 있는 힘의 장.
그림 2. 이 예시에서 다섯 개 가운데 세 개의 힘의 장을 고르는 최적의 선택.