13440번 - 귀

좌표 평면 위에 빨간 점 N개와 파란점 M개가 놓여져있다. 모든 빨간 점의 y좌표는 0이고 모든 파란 점의 y좌표는 0보다 크다.

수빈이는 이 점들을 이용해서 귀 모양을 만들려고 한다. 귀 모양은 서로 다른 빨간 점 4개 A, B, C, D와 서로 다른 파란 점 P, Q로 이루어져 있으며, 아래와 같은 3가지 조건을 만족해야 한다.

• 점 B와 C는 선분 AD의 내부에 있어야 한다.
• 각 PAD, PDA, QBC, QCB는 90도보다 작아야 한다.
• 점 Q는 삼각형 PAD 내부에 있어야 하며, 변 위에 있으면 안 된다.

빨간 점과 파란 점이 주어졌을 때, 귀 모양을 만들 수 있는 방법의 수를 구하는 프로그램을 작성하시오. 즉, 빨간 점 4개와 파란 점 2개가 귀 모양을 이루는 경우의 수를 구해야 한다.

첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 300)

둘째 줄에는 모든 빨간 점의 X 좌표가 주어진다.

셋째 줄부터 M개의 줄에는 파란 점의 X와 Y좌표가 주어진다.

입력으로 주어지는 모든 좌표는 10,000보다 작거나 같은 자연수이다.

첫째 줄에 귀 모양을 만들 수 있는 방법의 수를 출력한다.

예제 3의 경우에 P와 Q를 선택하는 방법은 아래와 같이 4가지가 있다.

• (5, 3), (3, 1)
• (6, 5), (3, 1)
• (8, 4), (3, 1)
• (6, 5), (5, 3)