메뉴 건너뛰기

문제

04nh3 농지 정리 0  

시간메모리제출 올바른 답 비율
1초64MB
3
2
66.7%


나의 횟수나의 최근 판정시도 성공 비율
32
66.7%
농지 정리 

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

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

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

입력

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

출력

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

예시
1입력
8 6
13
0 2 2 3
3 0 2 3
2 4 2 3
2 4 2 6
2 4 4 4
4 4 4 2
4 2 4 0
4 4 5 6
4 2 8 6
5 1 7 1
5 1 5 2
5 2 7 3
7 1 7 3
출력
13.0
위로