지도 이름표
시간 제한4초메모리 제한128 MB
각 점을 좌상단 꼭짓점으로 하는 가로세로 비율 3:1의 사각형들이 서로 겹치지 않도록 배치할 때 가능한 최대 높이를 구하는 문제입니다.
문제
현대 지도 제작에서 어려운 일 중 하나는 지명 이름표를 지도 위에 배치하는 것이다. 모든 도시, 마을, 촌락의 이름을 그대로 쓰면 이름표가 서로 겹쳐 지도를 읽기 어려워질 수 있다.
카르테시안 평면 위에 표시해야 할 점들의 좌표가 주어진다. 각 점에는 하나의 직사각형 이름표 영역을 배치해야 한다. 모든 이름표 영역의 변은 좌표축과 평행하고, 너비는 높이의 정확히 3배이다.
각 점마다 정확히 하나의 직사각형을 배치해야 하며, 그 점은 해당 직사각형의 왼쪽 위 꼭짓점이다. 즉, 이름표 영역은 점에서 오른쪽 아래 방향으로 놓인다. 모든 이름표 영역의 크기는 서로 같아야 한다.
모든 점에 이름표를 붙였을 때, 어떤 두 이름표 영역도 겹치지 않도록 할 수 있는 직사각형 높이의 최댓값을 구하라. 두 이름표는 변이나 꼭짓점에서 닿을 수는 있다.
주어지는 좌표는 0 이상 1,000,000 이하의 정수이다. 직사각형의 일부가 이 좌표 범위를 벗어나도 된다.
입력
첫째 줄에 지도 위 점의 개수 N이 주어진다. 2 ≤ N ≤ 100,000이다.
다음 N개의 줄에는 각 점의 좌표 X와 Y가 주어진다. 0 ≤ X, Y ≤ 1,000,000이며, 같은 좌표를 가진 두 점은 없다.
출력
첫째 줄에 직사각형의 높이를 실수로 출력한다. 답은 소수점 아래 두 자리까지 출력하면 된다.
출력한 값은 정답과의 절대 오차가 0.01 이하여야 한다.