Uzb Eng

0047. Katta kvadrat bolaklari
: 2 c
: 64

Anvarni tugilgan kuniga tomonlarni n va m bolgan togritortburchakli tort sobga qilishdi. Anvar kvadratni togritortburchaklardan kora yaxshi koradi. Albatta, u tortini koplab bir xil kvadrat bolakchalariga bolishga ahd qildi. Afsuski, uning ukasi Alisher undan oldin tortga yetib keldi va tortni parallel tomonlarini bir necha marta kesishga ulgurdi.
Anvarni bundan jahli chiqdi. Alisher uni ovutmoqchi. Buning uchun u kesib olingan bolaklardan mumkin bolgan olchamdagi maksimal kvadratlarni chiqarishi kerak. Boshida esa olingan bolakdan qanday eng katta olchamdagi kvadratni kesib olishini bilishi kerak. Alisherga yordam bering.

:
Birinchi satrda uchta n, (1 ≤ n,m ≤ 109, 0 ≤ ≤ 105) butun sonlar berilgan. Keyingi k ta satrda bolaklar berilgan. Har bir bolakda t va v sonlari berilgan. Dekart koordinalatalar sistemasini shunday kiritamizki, tortning bitta burchagi (0,0) , ikkinchi burchagi (n,m) bolsin. Demak, t = 0 bolganda oq boyicha bolak x = v (0 ≤ x ≤ n) sohani oz ichiga oladi, t=1 bolganda esa = v (0 ≤ y ≤ m) sohani.

:
Tort bolaklarga ajratilgandan keyin eng katta olchamdagi tomonlari kvadrat bolgan bolak sonini chiqaring.

10 10 2
1 5
0 3
4 7 0
5



4
:
: ( 2011).


Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.