# **Ancient Towers Solution**

https://codeforces.com/gym/103640/problem/A

Empezemos por leer el problema, obtener el número de cuadrilateros tal que su area seá mayor a 'S'.
Además notemos que nuestra complejidad puede tener un maximo de O(n^3logn).

Veamos una manera eficaz de contar los cuadrilateros según su area. Para ello, trazaremos una línea entre cualesquiera dos puntos y dividiremos el plano en dos partes, formando así triangulos los cuales podran emparejarse entre sí.
Para facilitar la explicación llamaremos al lado de puntos verde SideA y el otro SideB.
Ahora podemos notar con facilidad que podemos emparejar cualquier triángulo del SideA con cualquiera del SideB, pero para no exceder la complejidad permitida, realizaremos una técnica 'two pointers'.

Ordenaremos por su área (triangulo formado con A y B) tanto a SideA y SideB. Entonces hagamos lo siguiente, será 'i' = final de SideA y 'j' = inicio de SideB.

Si SideA[i] + SideB[j] >= 'S' entonces decrecemos a 'i' hasta que SideA[i] + SideB[j] < 'S', así podemos saber con facilidad cuantos triangulos en SideA formarán un cuadrilatero de área mayor a 'S' junto con el menor (en área) del SideB, cuando aumentamos en uno a 'j' tal que SideB[j + 1] >= SideB[j] sabemos que todos los triángulos que contamos para 'j' también contarán para 'j+1', así que solo necesitamos continuar la primer instrucción.

Dicho de otra manera
1. Si SideA[i] + SideB[j] >= S, i decrece en uno
2. Contar size_SideA - i - 1
3. Aumenatar en uno a j

Recapitulemos la complejidad, este ultimo procedimiento tiene una complejidad lineal aunado a los ordenamientos nos da O(nlogn), pero si recordamos que debemos trazar una recta entre cualquiera pareja de puntos, en realidad es O(n^3logn).

Sin embargo, hay algo que omiti, y es que con este método estamos contando todos los cudrilateros por una de sus diagonales, donde sabemos que los cuadriltaeros convexos poseen dos diagonales mientras que los cuadrilateros no convexos no.

Véamos un ejemplo.

Caso convexo
Notemos que es el mismo cuadrilatero y además que no importa cual recta se tome, se puede generar mediante la unión de dos triángulos.

Caso no convexo
Véase como contradice el método ya descrito y no puede obtenerse.

Así nos enfrentamos a una nueva problemática, debemos contar los convexos o no convexos por separado, para hacer un simple despeje. Llamemos a T como el resultado de la primer idea
Sea R = (T + no convexos) / 2 = (T - convexos)

Por conveniencia contaremos los no convexos.

Notemos que un cuadrilatero no convexo puede tener un único ángulo mayor a 180 grados (en caso de tener más excederia su suma interior de ángulos, 360), así que los contaremos buscando que tengan dicho angulo en el vertice A y B según la figura que hemos tratado hasta ahora (los puntos mediante los cuales dividimos el plano).
Ello podemos verlo si trazamos una recta desde un punto de cualquier lado hacia el punto A y B.
Así podemos checar que todos los puntos que esten a la derecha de la recta L,B formarán un cuadrilatero no convexo aunados a los que esten a la izquierda de la recta L,A.

Dado las circunstancias recurriremos a sweep line y más tarde a un BIT.

Primero descrubramos como contar los no convexos, dado que se tenemos el caso de tratat las rectas sobre A o B, lo haremos únicamente con B y el proceso con A es identico a excepción por los signos de la orientación.

Barreremos el plano con una recta que vaya desde el SideB a través de B, dado su orden polar respecto a la recta AB

De la siguiente manera





Ahora es sencillo notar que si emparejamos el triangulo desde el cual sale la recta (en SideB) con cualquier punto a la derecha de la recta (en SideA) formarán un poligono no convexo, además podemos usar la misma idea que hicimos para contar áreas, sabemos que conforme avanzamos en SideB, aquellos triángulos que emparejabamos y formaban un poligono no convexo también lo harán con los siguientes puntos en SideB.

Dicho de otra manera
Si SideA[i] esta a la derecha de la recta SideB[j],B entonces también lo estará para la recta SideB[j+1],B
(Se puede verificar si esta a la derecha con el signo del producto cruz).

Ahora sabemos contar los cuadrilateros no convexos, pero queremos los no convexos y que tengan área mayor a S.

Para ello añadiremos un punto al anterior proceso, y es que conforme vamos avanzando en el 'polar sort', podemos ir activando (como si de bits se tratará) las áreas de los triangulos formados a partir de los puntos que hemos visto que estan a la derecha de la recta e ir realizando una query para saber cuantas estan activadas tal que
SideA[i] >= S - SideB[j]
Esto se puede realizar si ordenamos el sideA segun sus áreas (triangulares formadas según SideA[i], A y B) y formar un BIT con dicho orden. Verificaremos los puntos en SideA que estan a la derecha respecto a la posición j en SideB (de la recta formada con B) y actualizaremos con un '1' en sus respectivas posiciones en el BIT, una vez teniendo todas las posiciones activadas, realizaremos una query (de suma) buscando la respuesta en el siguiente intervalo
[S - SideB[j], size_SideA]
La cual nos devolverá cuantos triángulos estan a la derecha (ya activados) y tienen área mayor a "S - SideB[j]".

Consecutivamente realizaremos el mismo proceso pero con el punto A. Almacenaremos dichos valores en U.

Recapitulemos la complejidad, sabemos que nuestro proceso de contar los cuadrilateros no convexos es idéntica al de contar áreas, sin embargo al agregarle el BIT, el proceso de contar se agrega un log(n), que no termina por afectar la complejidad final, obteniendo así O(n^3logn).

Finalmente obtendremos la respuesta R = (T + U) / 2.