MOG
Spanish
|
English

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

MOG Round #33

Ended

L - Pequeño triángulo

Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)

Existen muchos métodos para calcular el área de un triángulo. Por ejemplo, el área de un triángulo de base $b$ y altura $h$ es $\frac{bh}{2}$, y también puede representarse como $\sqrt{s(s - a)(s - b)(s - c)}$ donde $a$, $b$ y $c$ son las longitudes de sus lados y $s=\frac{a+b+c}{2}$. También hay muchos problemas relacionados con las áreas de triángulos. Tú probablemente has resuelto la mayoría de ellos pero no este.

Esta vez, debes encontrar el triángulo más pequeño en términos de área entre un conjunto $S$ de infinitos triángulos. Suena difícil ? Solo déjame hacer el problema un poco más simple agregando algunas limitaciones sobre $S$. Los triángulos en $S$ son exactamente todos los triángulos que tienen vértices en un conjunto $L$ con infinitos puntos en el plano en 2D. Todavía te resulta difícil ? Déjeme hacerlo aún más simple. El conjunto $L$ es determinado por $n$ vectores $v_1=(x_1, y_1), ..., v_n=(x_n, y_n)$ donde $x_1, ..., x_n, y_1, ..., y_n$ son enteros. $L$ es definido como sigue:

* $(0, 0) \in L$
* Si $(a, b) \in L$, entonces $(a + x_i, b + y_i) \in L$ y $(a - x_i, b - y_i) \in L$ para todo $i \in \{1, ..., n\}$.

Eso es, cualquier punto $(x,y) \in L$ si y solo si $(x, y)$ puede ser escrito como una combinación lineal entera de $v_1, ..., v_n$. Más precisamente,  $(x, y) = (z_1x_1 + ..., z_nx_n, z_1y_1 + ... + z_ny_n)$ para algunos enteros $z_1, ..., z_n$.

Ahora, creo que el problema es lo suficientemente fácil para ti.

Input

En la primera línea de entrada, hay un número entero $T$ $(T \leq 500)$ que indica el número de casos de prueba. La primera línea de cada caso de prueba contiene un número entero $n$ $(n \leq 100)$ que indica el número de vectores. La $i$-ésima de las siguientes $n$ líneas contiene dos enteros $x_i$ y $y_i$ donde $x_i, y_i \in [-10^9, 10^9]$ y $v_i = (x_i, y_i)$. Todos los puntos en el caso de prueba se pueden representar mediante una combinación entera de $v_1, ..., v_n$. Es decir, puede escribirse como $(z_1x_1 + ... + z_nx_n, z_1y_1 + ... + z_ny_n)$ para algunos enteros $z_1, ..., z_n$.

Output

Para cada caso de prueba, imprima el área del triángulo más pequeño con un error absoluto de $0.1$ o menos. Si estos puntos no pueden formar ningún triángulo, imprima $-1$ en su lugar.

Sample test(s)

Input
2 2 1 0 2 0 3 1 3 3 1 4 4
Output
-1 4.0