Curling Vacuno.


Submit solution

Points: 2 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

El curling vacuno es un popular deporte de clima frío jugado en las Mulimpiadas.

Como el curling estándar, en el deporte participan dos equipos, cada uno de los cuales desliza N piedras pesadas a través de una pista de hielo. Al final del juego, hay 2N piedras en la pista, cada una ubicada en un punto 2D distinto.

Sin embargo, la asignación de puntos en la versión vacuna es un poco curiosa. Se dice que una piedra está capturada si está contenida dentro de un triángulo cuyos vértices son piedras poseídas por el oponente (una piedra que esté en el borde de un triángulo también cuenta como capturada). El puntaje de un equipo es el número de piedras del oponente que están capturadas.

Por favor, ayude a calcular el puntaje final de un partido de curling vacuno, dadas las ubicaciones de las 2N piedras.

Entrada

  • Línea 1: El entero N (3 \leq N \leq 50,000).
  • Líneas 2..1+N: Cada línea contiene 2 enteros especificando las coordenadas x y de una piedra del equipo A (cada coordenada yace en el rango -40,000..+40,000):
  • Líneas 2+N..1+2N: Cada línea contiene 2 enteros especificando las coordenadas x y de una piedra del equipo B (cada coordenada yace en el rango -40,000..+40,000):

Salida

Dos enteros separados por espacio, dando los puntajes de los equipos A y B.

Ejemplo de Entrada

4
0 0
0 2
2 0
2 2
1 1
1 10
-10 3
10 3

Cada equipo posee cuatro piedras. El equipo A tiene las piedras en (0,0), (0,2), (2,0) y (2,2) y el equipo B tiene piedras en (1,1), (1,10), (-10,3) y (10,3).

Ejemplo de Salida

1 2

El equipo A captura la piedra de su oponente que está en (1,1). El equipo B captura las piedras de su oponente que están en las posiciones (0,2) y (2,2).

USACO 2014 January Contest, Gold Problem 1. Cow Curling.


Comments

There are no comments at the moment.