Działka [B]
Limit pamięci: 256 MB
Bajtazar od dziecka marzył o działce w Puszczy Bajtockiej.
Obecnie pracuje jako informatyk i wreszcie może sobie pozwolić na realizację
tego marzenia.
Spółka Lasy Bajtockie właśnie rozpoczęła sprzedaż działek w nowym
fragmencie puszczy, a Bajtazar zgłosił się jako pierwszy klient.
Ów fragment puszczy z lotu ptaka wygląda jak kwadrat o wymiarach
i rośnie w nim sosen.
Jako pierwszy klient Bajtazar ma do wyboru wiele ofert lokalizacji działki.
Każda z ofert ma postać prostokąta położonego w całości we fragmencie puszczy.
Bajtazar nie wie jeszcze, którą ofertę wybrać.
Po zakupie działki Bajtazar zamierza ogrodzić ją płotem.
Bajtazar jest oszczędny i chciałby, żeby płot był jak najkrótszy,
a zarazem ogradzał wszystkie drzewa rosnące na terenie działki.
To, w szczególności, oznacza, że nie cały teren prostokątnej działki musi
zostać ogrodzony.
Bajtazar wie również, że każdego roku będzie musiał odprowadzić
podatek gruntowy, którego wysokość będzie proporcjonalna do powierzchni
ogrodzonego obszaru działki.
I to głównie ten niemały podatek martwi Bajtazara.
Pomóż Bajtazarowi w podjęciu decyzji i oblicz, dla każdej zaproponowanej
przez Lasy Bajtockie lokalizacji działki, jak duża byłaby
powierzchnia ogrodzonego obszaru działki.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite oraz
(, ), oznaczające długość
boku fragmentu puszczy i liczbę sosen rosnących w tym fragmencie.
Każdy z kolejnych wierszy zawiera dwie liczby całkowite ,
(), oznaczające współrzędne punktu,
w którym znajduje się -ta sosna.
Możesz założyć, że w każdym punkcie znajduje się co najwyżej jedna sosna.
Kolejny wiersz wejścia zawiera jedną liczbę całkowitą
(), oznaczającą liczbę możliwych lokalizacji działki.
Każdy z kolejnych wierszy zawiera cztery liczby całkowite
, , , (, ),
opisujące prostokątną działkę .
Wyjście
Twój program powinien wypisać na wyjście wierszy;
-ty z tych wierszy powinien zawierać jedną liczbę rzeczywistą,
podaną z dokładnością do jednej cyfry po kropce dziesiętnej:
pole ogrodzonego obszaru działki przy wyborze -tej oferty.
Możesz założyć, że pole to będzie zawsze dodatnie.
Przykład
Dla danych wejściowych:
9 7
1 1
1 3
3 3
3 1
6 5
6 6
7 3
3
0 4 0 4
2 7 0 7
3 7 3 6
poprawną odpowiedzią jest:
4.0
10.0
6.0
Wyjaśnienie do przykładu: Rysunek przedstawia pierwsze dwie oferty lokalizacji działki
z zaznaczeniem ogrodzonego obszaru.
Autor zadania: Adam Karczmarz.