Fleksis

5
Latvijas Informātikas olimpiādes logo

Uzdevums no 2024. g. LIO valsts kārtas.

Stāsts

Meistars Matīss ir nopircis jaunu leņķa slīpmašīnu (tautā sauktu par fleksi) un tagad to izmēģina, veicot iezāģējumus taisnstūrveida flīzē. Varam uzskatīt, ka flīze ir N×MN \times M vienību liels taisnstūris un katrs zāģējums sākas no kādas malas veselas koordinātas un ir vai nu perpendikulārs malai, vai arī 45∘45^\circ vai 135∘135^\circ leņķī pret to. Katrs iezāģējums beidzas flīzes iekšpusē vai uz malas punktā ar veselām koordinātām. Diviem dažādiem iezāģējumiem ir ne vairāk kā viens kopīgs punkts.

Piemēram, attēlā parādīta flīze, kurai N=7N=7, M=8M=8 un veikti pieci iezāģējumi.

1. attēls: Iezāģējumu piemērs, kur flīze tiek sadalīta astoņās daļās.
1. attēls: Iezāģējumu piemērs, kur flīze tiek sadalīta astoņās daļās.

Uzrakstiet datorprogrammu, kas dotam flīzes un veikto iezāģējumu aprakstam nosaka daļu skaitu, kādā tiks sadalīta flīze!

Ievaddati

Pirmajā rindā atrodas flīzes platums, augstums un veikto iezāģējumu skaits; tie ir trīs naturāli skaitļi N≤109N \le 10^9, M≤109M \le 10^9 un K≤2000K \le 2000.

Nākamajās KK rindās dots iezāģējumu apraksts — pa vienam katrā rindā. Katrā rindā ir četri, ar tukšumzīmēm atdalīti, veseli nenegatīvi skaitļi xSx_S (0≤xS≤N)(0 \le x_S \le N), ySy_S (0≤yS≤M)(0 \le y_S \le M), xBx_B (0≤xB≤N)(0 \le x_B \le N) un yBy_B (0≤yB≤M)(0 \le y_B \le M). Iezāģējuma sākumpunkts atrodas uz flīzes kādas malas, un tā koordinātas ir (xS,yS)(x_S, y_S). Iezāģējuma beigu punkts atrodas flīzes iekšpusē vai uz malas, un tā koordinātas ir (xB,yB)(x_B, y_B). Neviena iezāģējuma sākumpunkts nesakrīt ar šī iezāģējuma beigu punktu.

Izvaddati

Izvaddatu vienīgajā rindā jābūt naturālam skaitlim - daļu skaits, kādā iegriezumu rezultātā tiks sadalīta flīze.

Apakšuzdevumi un to vērtēšana

#Apakšuzdevuma aprakstsPunkti
1.

Uzdevuma tekstā dotie trīs testi.

2
2.

Robežas: n,m,k≤30n, m, k \le 30.

10
3.

Visi iegriezumi veikti perpendikulāri flīzes malām.

10
4.

Visi iegriezumi veikti 45∘45^\circ vai 135∘135^\circ leņķī.

12
5.

Nav tāda punkta, kurā veikts vairāk par diviem iegriezumiem.

30
6.

Ierobežojums: k≤50k \le 50.

10
7.

Ierobežojums: k≤400k \le 400.

10
8.

Bez papildu ierobežojumiem.

16
Apakšuzdevumu punktu summa = 100.

Piemēri

Ievaddati

8 7 5 0 7 6 1 0 1 6 7 4 0 1 3 8 4 2 4 4 7 4 2 Kopēt kodu

Izvaddati

8 Kopēt kodu

Ievaddati

5 5 5 0 3 3 3 3 0 3 3 2 5 2 2 5 2 2 2 0 0 4 4 Kopēt kodu

Izvaddati

7 Kopēt kodu

Ievaddati

3 3 2 0 3 1 2 3 0 1 2 Kopēt kodu

Izvaddati

2 Kopēt kodu

1. apakšuzdevuma ievaddati

10 3 7 0 2 9 2 10 1 1 1 0 0 2 2 2 3 4 1 2 0 4 2 9 3 7 1 6 3 8 1 Kopēt kodu
5 5 11 1 5 1 1 2 5 2 1 3 5 3 1 4 5 4 1 0 3 1 4 0 2 2 4 0 1 3 4 0 0 4 4 1 0 4 3 2 0 4 2 3 0 4 1Kopēt kodu
8 9 9 0 9 4 5 0 4 3 1 0 3 5 8 0 1 7 8 1 0 6 5 3 0 1 2 3 0 7 4 6 0 2 4 8 3 4 7Kopēt kodu