Straza P82489


Statement
 

pdf   zip

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 NN (1≤N≤201\le N\le 20), el número de trincheras. Cada una de las siguientes NN líneas contiene la descripción de una trinchera: cuatro enteros positivos x1,y1,x2,y2x_1, y_1, x_2, y_2 (todos iguales o inferiores a 1000), donde x1x_1 y y1y_1 son las coordenadas de un extremo, mientras que x2x_2 y y2y_2 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++