문제 설명

IU와 콘의 보드게임

img

2017년 8월 5일, 다양한 방법으로 3단 고음을 마스터한 아이유는 신나게 놀기로 했다. 무엇을 할까 고민하던 그녀는 콘이 보드게임을 플레이하고 있는 것을 보고 흥미가 생겼다. 보드판은 다음과 같이 생겼다.

img

게임판에는 점 A, B, C 위치에 핀이 꼽혀 있으며 이 세 점은 게임판에서 가장 큰 삼각형을 이루고 있다. 고무줄이 세 개가 있는데 각각이 AB, BC, CA에 묶여 있어 삼각형 ABC를 그리고 있다. 이 커다란 삼각형 ABC 안에는 n개의 핀이 무작위로 꼽혀 있다.
이 게임은 세 개의 고무줄을 삼각형 ABC의 안쪽으로 이동시켜 새로운 도형을 만들어 내는 것이 목표이며, 그 과정에서 핀의 위치는 고정되어 움직일 수 없다. 삼각형 ABC 내부의 핀들과 고무줄의 물리적 특성에 의해 이러한 방식으로 만들어지는 도형들은 다음과 같은 성질을 갖는다.

  • 꼭짓점은 모두 어떤 핀에 의해 만들어지며 변은 핀과 핀 사이의 선분이 된다.
  • 끝점이 AB에 고정된 고무줄은 A에서 시작하여 B로 끝나는 안쪽으로 오목한 모양을 그리게 된다.
  • 끝점이 BC에 고정된 고무줄은 B에서 시작하여 C로 끝나는 안쪽으로 오목한 모양을 그리게 된다.
  • 끝점이 CA에 고정된 고무줄은 C에서 시작하여 A로 끝나는 안쪽으로 오목한 모양을 그리게 된다.

여기에 아래의 추가 조건을 만족하는 도형을 모두 찾고 싶다.

  • 임의의 두 고무줄이 서로 교차하지 않으며, 점 A, B, C를 제외한 곳에서 겹치지 않는다. 따라서 만들어지는 도형의 내부와 외부가 명확하게 구분된다.
  • 그 도형의 내부에 다른 핀이 존재하지 않는다.

img

위의 첫 번째 그림은 게임판의 시작 형태를 보여주고 있다. 여기에는 삼각형 ABC 안에 8개의 핀이 꼽혀 있으며, 세 개의 고무줄은 서로 다른 색으로 표현되어 있다. 두 번째 그림은 추가 조건 두 가지를 모두 만족하는 도형의 예를 보여준다. 세 번째와 네 번째 그림은 고무줄로 만들 수 있는 모양이지만 추가 조건을 만족시키지 못하는 예이다. 세 번째 도형은 두 고무줄이 교차하여 추가 조건 1을 만족하지 못하고 네 번째 도형은 추가 조건 1을 만족하지만 내부에 핀이 존재하여 조건 2를 만족하지 못한다.
위의 두 번째 도형과 같이 추가 조건 1과 2를 모두 만족하는 도형이 몇 개인지 맞히는 사람이 이기는 게임이다. 승부욕이 강한 아이유는 콘에게 지고 싶지 않아 여러분에게 도움을 요청했다. 삼각형 ABC 내부에 위치한 n개의 핀의 좌표가 주어질 때에 위의 조건을 만족하는 도형의 개수를 세는 프로그램을 작성하시오.

입력 형식

입력은 삼각형 내부의 핀의 개수 n, 삼각형의 좌표 triangle, 핀의 좌표 v 배열로 구성되어 있다. triangle3 × 2 크기의 2차원 배열이며, vn × 2 크기의 2차원 배열이다. 제한조건은 다음과 같다.

  • 0 <= n <= 500
  • trianglev의 원소인 x좌표와 y좌표는 모두 -100,000,000 이상 100,000,000 이하이다.
  • trianglev로 주어진 모든 점을 통틀어, 같은 좌표를 가진 두 핀이 입력으로 주어지지 않는다.
  • trianglev로 주어진 모든 점을 통틀어, 임의의 세 점이 하나의 직선 위에 놓이는 경우는 없다.

출력 형식

문제에 설명된 조건을 모두 만족하는 도형의 개수를 리턴한다.

예제 입출력

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를 만족하지 못한다.

실행 결과 실행 중지