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_29_06 - Konflikt

W Megabajtolandii zawsze panował ład i porządek. Jedyne państwa tej krainy - Bitocja i Bajtocja zajmowały równe powierzchnie i oddzielała je płynąca z zachodu na wschód rzeka. Ostatnio jednak doszło do konfliktu i wszyscy pragną mieć dla siebie cały układ współrzędnych.

Oba kraje chciałyby znać odległość do najbliżej położonego miasta przeciwnika. Ponieważ w tej krainie ludzie potrafią poruszać się tylko w czterech różnych kierunkach, interesuje nas odległość w sensie metryki miejskiej. Mając tą daną będzie wiadomo gdzie najszybciej przerzucić wojsko. Jako niezależny informatyk masz więc możliwość podwójnego zarobku! Napisz program który wyznaczy szukaną odległość, a będziesz mógł go sprzedać obu stronom konfliktu.

Wejście

Wejście rozpoczyna liczba testów 1 <= t <= 10. Każdy test zaczyna się liczbą 1 <= n <= 105 oznaczającą liczbę miast należących do każdej ze stron konfliktu. W kolejnych 2*n wierszach znajdują się współrzędne wszystkich miast - najpierw Bitocji, a później Bajtocji. Współrzędne podawane są w kolejnych liniach w postaci pary liczb całkowitych -109 <= x, y <= 109. Żadne dwa punkty nie pokrywają się. Dodatkowo miasta Bitocji spełniają y > 0, a miasta Bajtocji y < 0. Pliki z danymi wejściowymi nie przekraczają 7 MB.

Wyjście

Dla każdego testu należy wypisać odpowiedź w oddzielnej linii. Odpowiedzią jest minimalna odległość w metryce miejskiej pomiędzy parą miast należących do różnych stron konfliktu.

Przykład

Wejście:
2
3
-2 2
1 3
3 1
0 -1
-1 -2
1 -2
1
1 1
-1 -1

Wyjście: 5
4

Dodane przez:Adam Bąk
Data dodania:2016-08-25
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: ASM64 GOSU

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.