Капитан Сурок хочет подготовить огромную и важную битву против своего врага капитана Змеи. В этой битве у Сурка есть n полков, каждый полк состоит из 4 кротов.
Изначально каждый крот i (1 ≤ i ≤ 4n) стоит на некоторой позиции (xi, yi) на декартовой плоскости. Капитан Сурок хочет передвинуть некоторых кротов и сделать полки компактными, если это возможно.
У каждого крота i есть дом на месте (ai, bi). Чтобы один раз передвинуть крота, надо повернуть точку его местоположения (xi, yi) на 90 градусов против часовой стрелки относительно точки дома (ai, bi).
Полк компактный, только если точки местоположений 4 кротов лежат в вершинах квадрата ненулевой площади.
Помогите капитану Сурку найти для каждого полка минимальное количество ходов, необходимое, чтобы полк сделался компактным, если это возможно.
В первой строке записано единственное целое число n (1 ≤ n ≤ 100), количество полков.
В следующих 4n строках записано по 4 целых числа xi, yi, ai, bi ( - 104 ≤ xi, yi, ai, bi ≤ 104).
Выведите n строк. Если полк i можно сделать компактным, то в i-ой строке должно быть записано единственное целое число — минимальное количество требуемых ходов. В противном случае в i-ой строке выведите «-1» (без кавычек).
4
1 1 0 0
-1 1 0 0
-1 1 0 0
1 -1 0 0
1 1 0 0
-2 1 0 0
-1 1 0 0
1 -1 0 0
1 1 0 0
-1 1 0 0
-1 1 0 0
-1 1 0 0
2 2 0 1
-1 0 0 -2
3 0 0 -2
-1 1 -2 0
1
-1
3
3
В первом полку можно один раз передвинуть второго или третьего крота.
Второй полк сделать компактным не получается.
В третьем полку среди 3 последних кротов достаточно передвинуть один раз любого из них и два раза любого другого.
В четвертом полку можно два раза передвинуть первого крота и один раз — третьего крота.
| Codeforces Round 271 (Div. 2) |
|---|
| Закончено |
