군사 기지
시간 제한1초메모리 제한128 MB
최대 20개의 선분 참호가 주어질 때, 세 점이 서로 참호 위 선분으로 완전히 연결되고 그 사이에 다른 점이 끼지 않는 세 점 조합(순서 없음)의 개수를 구하는 문제입니다.
문제
평면 위에 여러 참호가 있다. 각 참호는 하나의 선분으로 나타낸다. 군인을 둘 수 있는 위치는 참호의 끝점이거나, 두 참호가 만나거나 교차하는 점이다.
밤에는 군인 세 명을 서로 다른 위치에 배치한다. 두 군인이 서로 볼 수 있으려면 두 군인을 잇는 선분 전체가 참호들의 합집합 위에 있어야 한다. 또한 세 번째 군인이 그 선분 위에서 두 군인 사이에 엄격히 있으면, 그 두 군인은 서로 볼 수 없다.
보안을 위해 세 군인의 모든 쌍이 서로 볼 수 있어야 한다. 가능한 배치의 수를 구하라. 세 군인은 서로 구별하지 않는다.
입력
첫째 줄에 참호의 수 N이 주어진다 (1 <= N <= 20).
다음 N개 줄에는 참호 하나의 양 끝점 (X1, Y1), (X2, Y2)를 나타내는 네 정수 X1 Y1 X2 Y2가 주어진다. 모든 좌표는 0 이상 1000 이하의 정수이다.
참호는 서로 겹칠 수 있고, 끝점을 공유할 수도 있다.
출력
군인 세 명을 배치하는 방법의 수를 출력한다.