Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
MOG Round #32Ended |
F - Fábrica de circunferencias
Languages: C, C++, Java, Haskell, JavaScript, Pascal, Tiger, Python, C#
Time & Memory limits: (details)
Fito es el encargado de la creación de circunferencias en la fábrica donde trabaja. Para crearlas, Fito escoge un punto sobre el eje X del cual surgirán todas las circunferencias. Al nacer, una circunferencia crece (aumentando su radio) hasta tocar un punto específico, que es distinto para cada circunferencia. Fito debe crear las circunferencias una a una, y no puede suceder que una de ellas, durante su crecimiento, toque a otra ya creada anteriormente. Por eso, Fito debe ser cuidadoso y analizará cómo ordenar las circunferencias. Él quiere saber de cuántas formas se pueden ordenar las circunferencias, tal que se pueda escoger algún punto inicial sobre el eje X y las circunferencias se creen sin violar las restricciones dadas.
Input
Línea 1
: Un entero $N$ $(1 \le N \le 10^3)$, indicando la cantidad de circunferencias.
Línea 2...N
: La $i$-ésima línea contiene las coordenadas enteras del punto $(x_i, y_i)$ $(1 \le x_i, y_i \le 100)$ el cual debe pertenecer a la $i$-ésima circunferencia de la entrada.
Output
Línea 1
: La cantidad de formas de ordenar las $N$ circunferencias de forma tal que existe, para cada orden, un punto inicial que hace posible la construcción de las circunferencias.
Sample test(s)
Hints
En el primer ejemplo, el orden $(1, 2)$ es válido si se escoge como punto de inicio de las circunferencias, por ejemplo, al punto $(10, 0)$. El orden $(2, 1)$ también es válido, escogiendo al punto $(0, 0)$.
En el segundo ejemplo los órdenes válidos son $(1, 2, 3)$, $(2, 1, 3)$, $(2, 3, 1)$ y $(3, 2, 1)$.