	2199 – Batalla del triangulo Asia - Dhaka - 2006/2007
	PDF		Submit		Ranking

J	Batalla del triangulo Input: Entrada estándar Output: Salida estándar

Es el año 2220, la gente no instala juegos de computador en su ordenador pues los juega en línea. “Battle of the triangle (Batalla del triangulo)” se ha convertido en el juego en línea mas popular en la red. En el juego se enfrentan dos ejércitos: el primero es controlado por 100 jugadores de una ciudad, mientras que el segundo por otros 100 jugadores de otra ciudad.

Al inicio del juego se echa a suerte un lanzamiento. El ganador del lanzamiento es designado como el Equipo A, mientras que el perdedor como el Equipo B. El campo de batalla se encuentra listo para los dos equipos. El campo de batalla es un plano bidimensional, en el cual las posiciones de los soldados están dadas por el Sistema Bidimensional de Coordenadas Cartesianas, y la posición de igual modo. Existen tres líneas de frontera las cuales encierran un triangulo, de tal modo que toda la parte interna del triangulo así formado pertenece al Equipo A y todo en las regiones contiguas pertenece al Equipo B, tal y como se muestra en la figura siguiente. Las tres regiones restantes son neutras. El Equipo A puede mover las líneas fronterizas para elegir si propio triangulo. Sin embargo el equipo no puede girar las líneas fronterizas.

Figura: La zona gris oscura es la región para A, la zona gris clara es la región para B y las zonas blancas son regiones neutras.

Para jugar, los usuarios deben conectarse a un servidor central, recalcando así que cada equipo consta de 100 jugadores.

Cada equipo tiene un capitán. El capitán del equipo A inicialmente escoge tres líneas de frontera. Cuando dichas líneas son escogidas, el servidor entrega al capitán del Equipo A un par de datos: la diferencia entre el numero de soldados de los equipos A y B, así como la diferencia entre la cantidad de tanques del equipo A y B, así el capitán puede replantear su estrategia. Sin embargo muchos equipos juegan alrededor del mundo al mismo tiempo usando el mismo campo de batalla, de modo que el servidor debe responder muchas preguntas simultáneamente. Tu trabajo es escribir un programa que realice esta tarea de manera muy eficiente.

Input (Entrada)

El archivo de entrada contiene varios sets de entrada. La descripción de cada set es como se indica:

Cada set empieza con tres enteros S, T y Q. S (0<S≤50000) es la cantidad total de soldados en el mapa, T (0<T≤50000) es el numero total de tanques en el mapa y Q (0<Q≤10000) es la cantidad de preguntas que el servidor tiene que procesar. Cada una de las S siguientes líneas contiene dos enteros x_i, y_i(|x_i|, |y_i|≤10000000) que denotan las coordenadas cartesianas de los soldados. Las T líneas siguientes contienen dos enteros x_j, y_j(|x_j|, |y_j|≤10000000) que denotan las coordenadas de los tanques. Estas líneas son seguidas por 3Q líneas en la cual cada pregunta consiste de tres líneas de input (entrada).

La primera línea contiene tres enteros ,, la segunda línea contiene tres enteros , y la tercer línea contiene tres enteros_. Significando así que el capitán del Equipo A ha situado la primera línea fronteriza a lo largo de la línea recta la segunda línea fronteriza en , y la tercera línea fronteriza en _-

De modo que la región para el equipo A es el triangulo formado por estas tres líneas rectas y la región para el equipo B son las tres regiones reciprocas de este triángulo. Para cada pregunta debes encontrar la diferencia de la cantidad de soldados entre el Equipo A y el Equipo B, así como la diferencia del numero de tanques entre el Equipo A y el Equipo B.

La figura antes mostrada corresponde a un ejemplo de entrada (Input). Puedes asumir que en un set de entrada la primera línea de cada pregunta es análoga a otra, siendo esto valido para la segunda línea de cada pregunta, así como para la tercera línea de cada pregunta. También puedes asumir que (), , ninguna de dos líneas en una pregunta son análogas entre ellas, las tres líneas en una pregunta son NO concurrentes, y ningún soldado, así como ningún tanque podrán estar en cualquiera de estas tres líneas fronterizas.

En el caso que S=T=Q=0, la entrada termina. Este caso no será procesado. El archivo de entrada pesa alrededor de 6MB. Estas pautas te darán alguna idea de cuan eficiente tu programa necesita ser.

Output (Salida)

Para cada set de entrada (input) se producen (Q+1) líneas de salida (outputs). La primera línea contiene la serie de campos de batalla. Cada una de las siguientes Q líneas contienen salida para pregunta. Por cada salida de pregunta en única línea la serie de preguntas son seguidas por dos enteros DS y DT separados por un espacio. DS es la diferencia del numero de soldados entre el Equipo A y el Equipo B, y DT es la diferencia del numero de tanques entre el Equipo A y el Equipo B. Aunque este problema no tenga múltiples respuestas, debido al comportamiento inestable de un numero en punto flotante habrá una diferencia de uno entre la solución propuesta por el jurado y la propuesta por usted, que será aceptada. Por lo cual existe un jurado particular para ese problema.

Sample Input Output for Sample Input

(ejemplo de entrada) (salida para ejemplo de entrada)

8 5 2

-1 8

-7 3

-2 1

-2 -1

-5 -2

6 -1

2 -4

-4 -5

1 7

1 1

3 4

-6 5

-12 -6

2 -2 10

-2 6 6

-5 -3 15

1 -1 5

1 -3 -3

5 3 -15

0 0 0

Battle Field 1:

Query 1: 1 -1

Query 2: 1 -1

La figura mostrada corresponde a un ejemplo de entrada.

Problem setter: Shahriar Manzoor

Dhaka 2006-2007

Traducido por: Max Héctor Izquierdo