Straza P82489


Statement
 

pdf   zip

thehtml

Cerca de una base militar hay varias trincheras, modeladas como segmentos de línea en el plano. Por la noche, cuando la mayoría de soldados están dormidos, tres soldados hacen guardia en las trincheras. Dos soldados se ven si el segmento de línea que los une está completamente dentro de una o más trincheras, y además el tercer soldado no está en medio.

Por razones de seguridad, los soldados deben situarse de tal modo que cada uno de ellos vea a los otros dos. ¿De cuántos modos pueden situarse?

Entrada

La primera línea contiene un entero N (1≤ N≤ 20), el número de trincheras. Cada una de las siguientes N líneas contiene la descripción de una trinchera: cuatro enteros positivos x1, y1, x2, y2 (todos iguales o inferiores a 1000), donde x1 y y1 son las coordenadas de un extremo, mientras que x2 y y2 son las coordenadas del otro extremo.

Ten en cuenta que en la entrada las trincheras se pueden superponer o compartir extremos.

Salida

Escribe el número de modos distintos en que es posible situar a los tres soldados.

Public test cases

  • Input

    6
0 0 1 0
0 0 0 1
1 0 1 1
0 1 1 1
0 0 1 1
1 0 0 1

    Output

    8

  • Input

    4
5 1 7 1
1 1 5 1
4 0 4 4
7 0 3 4

    Output

    1

  • Input

    3
2 2 3 2
3 2 3 3
3 3 2 3

    Output

    0
    • Information
    Author
    COCI06/07
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++