시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 8 3 2 33.333%

문제

좌표 평면 위에 빨간 점 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보다 작거나 같은 자연수이다.

출력

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

예제 입력 1

4 2
3 2 8 7
5 2
4 4

예제 출력 1

1

예제 입력 2

4 2
3 2 8 7
2 3
8 4

예제 출력 2

0

예제 입력 3

4 4
1 2 6 9
3 1
6 5
8 4
5 3

예제 출력 3

4

예제 입력 4

6 3
100 200 399 800 900 999
150 2
250 3
349 1

예제 출력 4

12

예제 입력 5

9 5
1 2 3 4 5 6 7 8 9
4 1
5 2
6 3
7 4
8 5

예제 출력 5

204

힌트

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

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

출처