2604번 - 농지 정리

현재 KOI 마을의 논들은 전체 모양이 직사각형인 토지를 아래의 그림과 같이 선분인 논둑을 경계로 나누어져 있다. KOI 마을의 김 하진 이장님은 마을 회의를 열어 논 관리와 벼농사를 효율적으로 하기 위해 각각의 논을 같은 면적의 직사각형 모양이 되도록 농지를 정리하기로 하였다. 이렇게 농지 정리를 하기 위해서는 현재 분할되어 있는 각 논들의 정확한 면적을 알아야 한다.

현재 분할된 논들을 표현하기 위해 마을 전체의 토지인 직사각형의 가로, 세로의 크기를 나타내는 정 수들 w와 h가 주어지고, 그리고 선분인 각 논둑의 양 끝점의 위치 (x₁, y₁)과 (x₂, y₂)가 주어져 있다. 여기서 마을 전체의 직사각형 토지의 왼쪽 아래 모퉁이의 위치는 (0, 0)이고, 오른쪽 위 모퉁이의 위치는 (w, h)이다.

분할된 모습이 위와 같이 주어진 KOI 마을의 논들 가운데 면적이 가장 큰 논의 면적을 계산하여 출력 하는 프로그램을 작성하시오. 여기서 논둑이 차지하는 면적은 0이라 가정한다. 위의 그림에서 면적이 가장 큰 논은 빗금 친 부분이고 그 면적은 13이다.

첫째 줄에는 마을 전체의 토지인 직사각형의 가로와 세로의 길이를 나타내는 두 정수 w와 h가 주어진다. (1 ≤ w, h ≤ 20,000) 둘째 줄에는 선분인 논둑의 개수 N이 정수로 주어진다. (1 ≤ N ≤ 4,000) 그 다음 N줄에는 각 줄에 논둑의 양 끝점의 위치를 나타내는 네 정수 x₁, y₁, x₂, y₂가 한 줄로 주어진다. (0 ≤ x₁, x₂ ≤ w, 0 ≤ y₁, y₂ ≤ h) 각 선분은 양 끝점 외에는 다른 선분과 만나지 않는다.

입력으로 주어진 분할된 논들 가운데 면적이 가장 큰 논의 면적을 계산하여 출력하면 된다. 면적은 소수점 이하 한자리까지 계산한다.