Rectangular Pasture.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python, VB

El mayor pastizal del Granjero Juan puede ser representando como una cuadrícula 2D de "celdas" cuadradas (imagine un tablero de ajedrez enorme). Actualmente, hay N vacas ocupando algunas de esas celdas (1 \leq N \leq 2500).

El Granjero Juan quiere construir una cerca que encerrará una región rectangular de celdas; el rectángulo debe estar orientado de manera que sus lados sean paralelos a los ejes x y y, y podría ser tan pequeño como una sola celda. Por favor ayúdelo a contar el número de distintos subconjuntos de vacas que puede encerrar en una de tales regiones. Note que el conjunto vacio puede ser contado como uno de ellos.

Entrada

La primera línea contiene un solo entero N. Cada una de las siguientes N líneas contiene dos enteros separados por espacio, indicando las coordenadas (x, y) de la celda de una vaca. Todas las coordenadas x son distintas de las otros, y todas las coordenadas y son distintas de las otras. Todos los valores de x y de y están en el rango 0...10^9.

Salida

El número de subconjutos de vacas que GJ puede cercar. Se puede demostrar que esta cantidad entrará en un entero de 64 bits con signo (esto es un "long long" en C/C++).

Ejemplo de Entrada

4
0 2
1 0
2 3
3 5

Ejemplo de Salida

13

Explicación

Hay en total 2^4 subconjuntos. FJ no puede crear un cerco encerrando solamente a las vacas 1, 2, y 4, o solamente a las vacas 2 y 4, o solamente a las vacas 1 y 4, entonces la respuesta es 24 - 3 = 16 - 3 = 13.

Calificación

Los casos de prueba 2-3 satisfacen  N \leq 20

Los casos de prueba 4-6 satisfacen  N \leq 100

Los casos de prueba 7-12 satisfacen  N \leq 500

Los casos de prueba 13-20 no satisfacen restricciones adicionales.


Comments

There are no comments at the moment.