지도
시간 제한2초메모리 제한128 MB
각 도시 좌표를 왼쪽 위 꼭짓점으로 하는 3:1 비율 직사각형 라벨들이 겹치지 않도록, 배치 가능한 최대 높이를 구하는 문제입니다.
문제
도시 이름을 지도에 겹치지 않게 배치하려고 한다.
각 도시의 위치는 (x, y) 좌표로 주어진다. 모든 도시 이름은 같은 크기의 직사각형 안에 쓰며, 직사각형의 가로 길이는 세로 길이의 3배이다. 한 도시의 직사각형은 그 도시 좌표를 왼쪽 위 꼭짓점으로 삼아 오른쪽 아래 방향으로 놓인다. 예를 들어 도시가 (5, 3)에 있고 직사각형의 가로 길이가 3, 세로 길이가 1이면, 직사각형은 (5, 3)에서 (8, 2)까지의 영역에 놓인다.
두 직사각형은 점이나 선분만 공유할 수 있다. 양의 넓이를 가지는 부분이 서로 겹치면 안 된다.
모든 도시에 이름을 붙일 수 있도록 하는 직사각형의 최대 세로 길이를 구하시오. 직사각형의 가로 길이는 항상 그 값의 3배이다.
입력
첫째 줄에 도시의 개수 n이 주어진다. (2 ≤ n ≤ 100,000)
다음 n개의 줄에는 각 도시의 좌표를 나타내는 두 음이 아닌 정수 x, y가 주어진다. (0 ≤ x, y ≤ 1,000,000)
서로 다른 두 도시는 같은 좌표로 주어지지 않는다.
출력
첫째 줄에 가능한 직사각형의 최대 세로 길이를 출력한다.
소수점 셋째 자리에서 반올림하여 소수점 둘째 자리까지 출력한다. 항상 소수점 아래 두 자리를 모두 출력해야 한다.