문제 설명
IU와 콘의 보드게임
2017년 8월 5일, 다양한 방법으로 3단 고음을 마스터한 아이유는 신나게 놀기로 했다. 무엇을 할까 고민하던 그녀는 콘이 보드게임을 플레이하고 있는 것을 보고 흥미가 생겼다. 보드판은 다음과 같이 생겼다.
게임판에는 점 A
, B
, C
위치에 핀이 꼽혀 있으며 이 세 점은 게임판에서 가장 큰 삼각형을 이루고 있다. 고무줄이 세 개가 있는데 각각이 A
와 B
, B
와 C
, C
와 A
에 묶여 있어 삼각형 ABC
를 그리고 있다. 이 커다란 삼각형 ABC
안에는 n
개의 핀이 무작위로 꼽혀 있다.
이 게임은 세 개의 고무줄을 삼각형 ABC
의 안쪽으로 이동시켜 새로운 도형을 만들어 내는 것이 목표이며, 그 과정에서 핀의 위치는 고정되어 움직일 수 없다. 삼각형 ABC
내부의 핀들과 고무줄의 물리적 특성에 의해 이러한 방식으로 만들어지는 도형들은 다음과 같은 성질을 갖는다.
- 꼭짓점은 모두 어떤 핀에 의해 만들어지며 변은 핀과 핀 사이의 선분이 된다.
- 끝점이
A
와B
에 고정된 고무줄은A
에서 시작하여B
로 끝나는 안쪽으로 오목한 모양을 그리게 된다. - 끝점이
B
와C
에 고정된 고무줄은B
에서 시작하여C
로 끝나는 안쪽으로 오목한 모양을 그리게 된다. - 끝점이
C
와A
에 고정된 고무줄은C
에서 시작하여A
로 끝나는 안쪽으로 오목한 모양을 그리게 된다.
여기에 아래의 추가 조건을 만족하는 도형을 모두 찾고 싶다.
- 임의의 두 고무줄이 서로 교차하지 않으며, 점
A
,B
,C
를 제외한 곳에서 겹치지 않는다. 따라서 만들어지는 도형의 내부와 외부가 명확하게 구분된다. - 그 도형의 내부에 다른 핀이 존재하지 않는다.
위의 첫 번째 그림은 게임판의 시작 형태를 보여주고 있다. 여기에는 삼각형 ABC
안에 8개의 핀이 꼽혀 있으며, 세 개의 고무줄은 서로 다른 색으로 표현되어 있다. 두 번째 그림은 추가 조건 두 가지를 모두 만족하는 도형의 예를 보여준다. 세 번째와 네 번째 그림은 고무줄로 만들 수 있는 모양이지만 추가 조건을 만족시키지 못하는 예이다. 세 번째 도형은 두 고무줄이 교차하여 추가 조건 1을 만족하지 못하고 네 번째 도형은 추가 조건 1을 만족하지만 내부에 핀이 존재하여 조건 2를 만족하지 못한다.
위의 두 번째 도형과 같이 추가 조건 1과 2를 모두 만족하는 도형이 몇 개인지 맞히는 사람이 이기는 게임이다. 승부욕이 강한 아이유는 콘에게 지고 싶지 않아 여러분에게 도움을 요청했다. 삼각형 ABC
내부에 위치한 n개의 핀의 좌표가 주어질 때에 위의 조건을 만족하는 도형의 개수를 세는 프로그램을 작성하시오.
입력 형식
입력은 삼각형 내부의 핀의 개수 n
, 삼각형의 좌표 triangle
, 핀의 좌표 v
배열로 구성되어 있다. triangle
은 3 × 2
크기의 2차원 배열이며, v
는 n × 2
크기의 2차원 배열이다. 제한조건은 다음과 같다.
0 <= n <= 500
triangle
과v
의 원소인x
좌표와y
좌표는 모두-100,000,000
이상100,000,000
이하이다.triangle
과v
로 주어진 모든 점을 통틀어, 같은 좌표를 가진 두 핀이 입력으로 주어지지 않는다.triangle
과v
로 주어진 모든 점을 통틀어, 임의의 세 점이 하나의 직선 위에 놓이는 경우는 없다.
출력 형식
문제에 설명된 조건을 모두 만족하는 도형의 개수를 리턴한다.
예제 입출력
n | triangle | v | answer |
---|---|---|---|
2 | [[0, 8], [-4, 0], [4, 0]] | [[-1, 3], [1, 4]] | 6 |
10 | [[-13, 40], [-27, -48], [31, 6]] | [[2, 21], [15, -1], [6, -13], [-20, -27], [5, 9], [5, 11], [-18, -26], [-15, 19], [7, 4], [-5, -18]] | 73 |
예제에 대한 설명
첫 번째 예제에는 삼각형의 꼭짓점을 제외하고 총 2개의 핀의 위치가 주어졌다. 삼각형의 좌표를 A(0, 8)
, B(-4, 0)
, C(4, 0)
, 그리고 삼각형 내부의 핀을 D(-1, 3)
, E(1, 4)
라고 하자. 고무줄로 만들 수 있으면서 추가 조건 1, 2를 만족하는 도형은 총 6개로 아래와 같다.
사각형 ABCD
, 사각형 AEBC
, 오각형 ADBCE
, 오각형 ABDCE
, 오각형 ADBEC
, 오각형 ABDEC
그 외의 도형은 모두 추가 조건 1 혹은 추가 조건 2를 만족하지 못한다.