Aveți o foaie de hârtie dreptunghiulară cu dimensiunile N x M
centimetri. Foaia este împărțită într-o rețea de pătrate de 1 x 1
centimetri fiecare. Puteți considera foaia ca un sistem de coordonate – colțul din stânga jos este originea (0,0)
a sistemului de coordonate și fiecărui vârf al unui pătrat îi sunt atribuite coordonate întregi – între 0
și N
pe axa x
și între 0
și M
pe axa y
. Primiți o succesiune de cereri de tăiere a foii de hârtie (sau mai exact, a părții care a mai rămas din ea). Fiecare cerere este definită de o pereche de numere întregi nenegative (p, q)
, reprezentând un punct din rețea, care este situat în porțiunea netăiată a hârtiei. Tăierea se execută după următorul algoritm: se desenează două segmente, ambele începând din punctul (p, q)
, unul la un unghi de 45°, iar celălalt la un unghi de 135° față de axa x
, îndreptat “în sus”, adică cu y
crescător. Ambele segmente se termină la marginea foii dreptunghiulare de hârtie. După aceea, porțiunea de hârtie care se află deasupra segmentelor desenate este tăiată, iar restul de hârtie rămâne ca o figură nouă (vezi imaginile exemplu)
Aveți mai jos un exemplu ce pornește cu o hârtie dreptunghiulară cu dimensiunile N = 20
și M = 10
, precum și toate figurile care rămân după ce urmează cererile de tăiere:
(10,5)
– partea albastră este tăiată(4,7)
– partea roșie este tăiată(0,1)
– partea verde este tăiată(16,3)
– partea maro este tăiată
Cerința
Scrieți un program care după fiecare cerere calculează aria figurii rămase. Important: Este posibil să primiți o cerere care va defini unul dintre segmente cu lungime 0
, de exemplu dacă punctul este situat pe marginea din stânga sau din dreapta dreptunghiului. Cu toate acestea, este garantat că fiecare cerere va duce la tăierea unei figuri de suprafață pozitivă.
Date de intrare
De pe prima linie a intrării standard citiți două numere întregi pozitive N
și M
– dimensiunile foii inițiale de hârtie. De pe a doua linie citiți un întreg pozitiv Q
– numărul de cereri de tăiere. De pe ultimele Q
linii citiți două numere întregi nenegative x
și y
, separate prin spațiu – coordonatele punctului care definește o cerere de tăiere.
Date de ieșire
Pentru fiecare cerere de tăiere, pe o linie separată, programul vostru va scrie un număr – aria figurii de hârtie rămase după tăiere. Valoarea ariei trebuie tipărită cu două cifre după virgula zecimală..
Restricții și precizări
1 ≤ N × M ≤ 10
12
1 ≤ Q ≤ 150.000
- Datorită mărimii testelor, unele dintre ele au fost omise
Exemplu:
Intrare
20 10 4 10 5 4 7 0 1 16 3
Ieșire
175.00 167.00 138.50 103.00
Explicație
Este exemplul din enunț