URI Online Judge | 1027

Ola Crítica

Por Monirul Hasan Tomal, Southeast University Bangladesh

Timelimit: 2

La tarea es simple. A través de algunos puntos críticos en 2D, usted tiene que dibujar una onda como curva. Su objetivo es incluir tantos puntos como sea posible.


Dos puntos consecutivos en la curva deben tener una diferencia de 2 entre sus coordenadas y.

Entrada

No habrá más de 222 casos de prueba. Cada caso de prueba comienza con un número entero N, el número de puntos en el caso de prueba. En las siguientes N líneas, habrá N par de enteros indicando la coordenada x e y de los puntos. No habrá más de 1000 puntos en cada caso de prueba. Todas las coordenadas son números enteros - encajarían en un entero de 2 bytes. Los datos deben ser leídos de entrada standard.

Salida

Para cada caso de prueba imprimir un número - el número máximo de puntos críticos que se pueden incluir en una curva dibujada por los puntos dados.

Ejemplo de entrada Ejemplo de salida

10
0 1
1 0
1 -1
2 -2
3 1
3 -1
3 -2
4 1
4 -1
5 -1
10
0 2
2 0
1 -1
2 -2
3 1
3 -1
3 -2
4 1
4 -1
5 –1

4
3