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.|

FR_07_12 - Czerwone mrówki

Czerwone mrówki

Przyrodnik Jasiu postanowił zbadać wścieklice, mrówki popularnie nazywane czerwonymi. W tym celu udał się do pobliskiego lasu, aby je poobserwować. Zdziwił się trochę, gdy zauważył, że kolonia czerwonych mrówek wymieszała się z kolonią rudnic. Postanowił zrobić trochę zdjęć. Po powrocie do domu zabrał się do analizowania zrobionych przez siebie zdjęć. Naszego przyrodnika interesuje, jaka jest liczebność wszystkich mrówek w najmniejszym prostokątnym obszarze, do którego należą wszystkie mrówki czerwone. Boki takiego prostokątnego obszaru muszą być równoległe do osi układu współrzędnych. Każda mrówka na zdjęciu opisana została za pomocą współrzędnych kartezjańskich oraz wartości 1 albo 0, gdzie 1 oznacza mrówkę czerwoną, a 0 oznacza mrówkę czarną. Teraz wystarczy już tylko napisać program, aby zaoszczędzić naszemu przyrodnikowi trochę czasu.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę zestawów danych - zdjęć. W pierwszym wierszu każdego zestawu znajduje się liczba całkowita n (2 ≤ n ≤ 105) oznaczająca liczebność mrówek na zdjęciu. W kolejnych n wierszach podane są po trzy liczby całkowite x, y, k (0 ≤ x, y ≤ 103, k={0,1}), gdzie wartości x, y oznaczają współrzędne kartezjańskie mrówki, a k to jej kolor. Dla k = 1 mrówka jest czerwona, dla k = 0 mrówka jest czarna. Można założyć, że żadna mrówka nie łazi po innej mrówce oraz, że rozmiar plików wejściowych nie przekracza 4 MB.

Wyjście
Dla każdego zestawu należy wypisać w osobnym wierszu jedną liczbę - liczebność wszystkich mrówek zawierających się w najmniejszym prostokątnym obszarze, do którego należą wszystkie mrówki czerwone.


Przykład

Wejście
1
9
6 3 1
1 2 0
7 2 0
5 1 1
2 5 0
4 4 0
1 4 1
3 3 0
5 7 0

Wyjście
6

Rysunek do przykładu
Mrówki czerwone jak i brzeg prostokątnego obszaru został oznaczony kolorem czerwonym. W prostokącie tym znajduje się łącznie sześć mrówek.


Dodane przez:Mariusz Śliwiński
Data dodania:2017-04-07
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.