3051번: 군사 기지

3051번: 군사 기지 - 계산 기하

N개의 선분이 주어질 때, 세 명의 사람이 한 선분 위에 있지 않으나

세 명의 사람이 이어져 있을 수 있는 방법의 가지 수를 묻는 문제이다.

즉 쉽게 얘기하면 N개의 선분을 그렸을 때 그 위에서 찾을 수 있는 삼각형의 개수이다.

처음에는 N개의 선분에서 3개를 골라 이들이 삼각형을 이루는 지 확인하였다.

선택한 세 선분 a, b, c로 삼각형을 만들 수 있는 지 확인하는 방법은 다음과 같이 진행하였다.

1. a와 b, b와 c, c와 a는 교점을 가진다.

2. a와 b의 교점이 c 위에 있어서는 안된다.

이렇게 문제에 접근 할 경우 문제가 되는 경우는 평행한 두 선분이 합쳐질 수 있을 때이다.

즉, a = (0, 2), b = (0, 4), c = (0, 3), d = (0, 5)에서

선분 ab와 선분 cd는 선분 ad라는 선분으로 합칠 수 있다.

모든 선분에 대해 더이상 합칠 수 없을 때까지 반복하여 평행한 겹치는 두 선분들을

한 선분으로 만들어 준 뒤 그 선분들 중 세 선분을 선택하여 삼각형을 만들 수 있는 지 확인하며 되는 문제이다.