Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_23_08 - Zielona trawka

W ten piękny słoneczny dzień profesor Algobit zabrał swoich studentów na przechadzkę po akademickim lesie, w którym może znajdować się nawet 10 000 pięknych zielonych drzew - głównie sosny i brzozy. Wykładowca ma dziś bardzo dobry humor i postanowił, że zaliczy całej grupie ćwiczenia z programowania równoległego pod warunkiem, że studenci znajdą największy niezalesiony obszar obrośnięty zieloną trawką. Dodatkowo obszar ten musi być w kształcie kwadratu, a jego boki muszą być równoległe do płotu, który otacza owy las. Studenci żwawo zabrali się do pracy. Szybko okazało się, że możliwości jest tak dużo, że bez twoich programistycznych umiejętności się nie obejdzie. Napisz program, nim skończy się ten piękny dzień, który znajdzie długość boku największego takiego kwadratu.

Wejście

W pierwszym wierszu jedna liczba określająca liczbę zestawów danych (nie więcej niż 10).

Specyfikacja każdego zestawu testowego:

w pierwszym wierszu cztery liczby całkowite xA, yA, xB, yB określające współrzędne naprzeciwległych wierzchołków prostokąta, który wyznacza ogrodzenie akademickiego lasu. Boki tego prostokąta są równoległe do osi współrzędnych (xA < xB, yA < yB)

Następnie jedna liczba n określająca liczbę drzew mieszczących się w ogrodzeniu.

Następnie n wierszy, w każdym wierszu po dwie liczby całkowite określające współrzędne drzew. Wszystkie współrzędne mieszczą się  w przedziale [0..106].

Wyjście

Dla każdego zestawu jedna liczba określająca długość boku największego kwadratu. Boki kwadratu muszą być równolegle do osi współrzędnych.

Przykład

Wejście:
1
0 0 5 6
3
1 1
5 3
3 5

Wyjście:
4

Wyjaśnienie przykładu:

zielona trawka

Szukany kwadrat nie może wychodzić poza granice ogrodzenia. Średnica drzewa jest pomijalnie mała.


Dodane przez:Marcin Kasprowicz
Data dodania:2015-06-03
Limit czasu wykonania programu:1s-3s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.