루미 알고리즘

#1269플래티넘Ett markant problem

PO 2002 결선코딩스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

(그림은 원문 저장소에서 볼 수 있습니다)

Storbonden Sven äger ett stort staketinhägnat rektangulärt område mark. Han har låtit dela upp marken i flera mindre områden genom att bygga staket så att varje mindre område är helt inhägnat av staket. Samtliga staket är raka och placerade parallellt med ytterkanterna. Nu ska Svens äldste son, Peter, gifta sig, och som bröllopspresent kommer han då få ett av dessa mindre områden. Peter vill självfallet ha det största området (sett till arean), men då Sven har varit klurig och delat in sin mark på ett komplicerat sätt är det inte helt enkelt att avgöra vilket område som är störst. Hjälp Peter att lösa problemet genom att skriva ett program som beräknar vilken del som har störst area.

Indata

Den första raden innehåller tre heltal, b, h (0 < b, h ≤ 40000) och n (4 ≤ n ≤ 50), där b och h anger bredden respektive höjden på Svens markområde och n anger antalet staket på Svens mark.

Därefter följer n stycken rader med fyra heltal på varje rad, x_1, y_1, x_2, y_2 (0 ≤ x_1, x_2 ≤ b och 0 ≤ y_1, y_2 ≤ h) som anger start- och ändpunkten på ett staket. Det nedre vänstra hörnet på Svens område har koordinaterna (0, 0) och det övre högra koordinaterna (b, h). Du kan anta att de fyra staketen, som inhägnar hela Svens område, är med i listan över staket, samt att inga staket korsar eller överlappar varandra.

Utdata

Skriv ut ett heltal: arean av det största området.

예제

예제 1

입력
13 8 12
0 0 13 0
13 0 13 8
13 8 0 8
0 8 0 0
5 0 5 5
5 5 3 5
3 5 3 8
5 3 9 3
9 3 9 8
11 4 13 4
11 4 11 6
11 6 13 6
출력
40

예제 2

입력
5 5 8
0 0 5 0
5 0 5 5
5 5 0 5
0 5 0 0
1 1 4 1
4 1 4 4
4 4 1 4
1 4 1 1
출력
16

출처 표기

출처: Programmeringsolympiaden 2002년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.