Barrenillo
Desde que heredé el terrenito de los abuelos plagado de higueras, el final del verano me lo paso haciendo mermelada. Pero este año pinta mal. He visto unos agujerillos en la corteza de muchos de los árboles y me han dicho que es barrenillo, un insecto insufrible que se come la madera y termina matando al árbol.
Como no quiero quedarme sin mermelada, he buscado medidas para acabar con la plaga que no afecten al árbol (ni a los higos) y me han hablado de un sistema de ultrasonidos. Cuesta un montón, así es que para probar, me he comprado solo un aparato, que emite un sonido que, supuestamente, mata al barrenillo. Tengo que decidir dónde lo coloco para que cubra el mayor número de higueras posible y así poder saber si funciona o no antes de continuar con mi inversión comprando más.
Por la disposición del terreno, solo puedo colocarlo en algún punto a lo largo de la muralla sur, apuntando exactamente hacia el norte. Los ultrasonidos se emiten únicamente en un cono de 90 grados de ancho, y solo las higueras que caigan dentro, o justo en el límite, recibirán el tratamiento.
Entrada
Cada caso de prueba comienza con un número 1 ≤ N ≤ 200.000 indicando el número de higueras en el terreno. A continuación vendrán N parejas de números, cada una indicando la posición (x, y) de una higuera. Ambos números serán enteros entre 1 y 109.
La entrada termina con un 0, que no deberá procesarse.
Salida
Por cada caso de prueba el programa indicará el mayor número de higueras que pueden cubrirse con un único dispositivo de ultrasonidos. El dispositivo solo puede colocarse en la parte sur (coordenada y = 0) apuntando hacia el norte, cubriendo 45 grados a cada lado de la vertical.
Por simplicidad, las higueras se consideran de radio cero, por lo que si una queda colocada en el borde de la visibilidad, se verá afectada por el tratamiento. Además, los ultrasonidos atraviesan la madera, por lo que un árbol no tapa a otro que quede detrás.
Entrada de ejemplo
6 1 2 2 1 3 3 5 1 2 4 2 3 3 1 1 3 1 4 2 0
Salida de ejemplo
5 3