Bajtlantydzkie miasta [B]
Limit pamięci: 64 MB
"Odcinek jest najkrótszą drogą łączącą dwa punkty" - to hasło było
główną motywacją dla projektantów dróg w Cesarstwie Bajtlantydy.
Z tego powodu wszystkie budowane tam drogi były proste i prowadziły przez cały kraj.
W każdym miejscu, w którym krzyżowały się dwie drogi, Bajtlantydzi zakładali miasto.
Aby uniknąć nieporozumień, Bajtlantydzi nigdy nie prowadzili więcej niż
dwóch dróg przez jeden punkt.
Cesarz Bajtlantydy chce teraz podzielić swoje państwo na dwie prowincje, w miarę
możliwości równe pod względem liczby miast.
Granicą prowincji zamierza ustanowić jedną z dróg Cesarstwa.
Miasta na drodze granicznej nie będą podlegać żadnej z prowincji, ale
bezpośrednio Cesarzowi.
Cesarz chciałby sprawdzić, dla każdej drogi, jaka jest wartość bezwzględna różnicy
między liczbami miast po jednej i po drugiej stronie tej drogi.
Bajtazar, nadworny kartograf, spędził wiele dni, wykonując polecenie dane mu przez Cesarza.
Twoim zadaniem jest napisanie programu, który pomoże mu w pracy.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita
(), oznaczająca liczbę dróg w Cesarstwie.
W kolejnych wierszach znajdują się opisy poszczególnych dróg w postaci
czwórek liczb całkowitych , , ,
(, punkty i
nie pokrywają się),
pooddzielanych pojedynczymi odstępami.
Każda taka czwórka opisuje jedną drogę, która jest prostą przechodzącą
przez punkty i .
Żadne dwie drogi nie pokrywają się. Żadne trzy drogi nie przecinają się w jednym punkcie.
Zakładamy, że Cesarstwo jest na tyle duże, że wszystkie przecięcia prostych
wyznaczających drogi leżą w jego granicach.
Wyjście
Na standardowe wyjście wypisz wierszy, zawierających odpowiedzi dla dróg
podanych na wejściu (w tej samej kolejności).
Odpowiedzią dla danej drogi jest wartość bezwzględna różnicy liczby miast
po jej dwóch stronach.
Przykład
Dla danych wejściowych:
4
1 -1 1 10
0 0 1 0
2 0 2 1
4 4 -1 -1
poprawną odpowiedzią jest:
1
2
3
2
W tym przykładzie mamy pięć miast o współrzędnych , , , i .
Autor zadania: Jakub Onufry Wojtaszczyk.