아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

보물찾기

시간 제한10초메모리 제한256 MB

요약
하나의 직선으로 모든 지뢰를 반대쪽에 가두고 같은 쪽에 남는 보물 수를 가장 크게 구합니다.
난이도

보통10점 중 7점

유형
기하, 완전 탐색
정답자
아직 제출이 없습니다

문제

섬에 보물 NN개와 지뢰 MM개가 묻혀 있다. 지뢰를 하나씩 해체하는 방법은 너무 위험하니, 대신 곧은 울타리를 하나 세워 지뢰가 있는 구역과 보물찾기를 할 구역을 나누기로 했다.

울타리는 두께가 없고 양쪽으로 무한히 뻗은 직선이며, 섬은 볼록하다고 본다. 울타리를 세우면 섬이 두 구역으로 나뉘고, 지뢰가 하나도 없는 구역의 보물만 안전하게 찾을 수 있다. 울타리 위에 보물이나 지뢰가 놓여서는 안 된다.

울타리를 하나 세울 때 지뢰가 없는 구역에 둘 수 있는 보물의 최대 개수를 구하시오.

입력

첫 줄에 테스트 케이스의 개수 TT가 주어진다.

각 테스트 케이스의 첫 줄에는 보물의 개수 NN과 지뢰의 개수 MM이 주어진다. 다음 두 줄에는 각각 정수가 NN개씩 주어진다. 첫 줄의 ii번째 정수는 ii번째 보물의 xx좌표이고, 둘째 줄의 ii번째 정수는 그 보물의 yy좌표이다. 이어지는 두 줄에는 각각 정수가 MM개씩 주어지며, 같은 방식으로 지뢰의 xx좌표와 yy좌표를 나타낸다.

  • 0<T≤100 < T \le 10
  • 1<N≤3001 < N \le 300
  • 1<M≤3001 < M \le 300
  • 모든 좌표는 0≤x,y≤1060 \le x, y \le 10^6인 정수이다.
  • 같은 위치에 두 물체가 놓이는 경우는 없다.
  • 울타리 위에는 보물도 지뢰도 놓이지 않는다.

출력

각 테스트 케이스마다 울타리 하나로 지뢰와 분리할 수 있는 보물의 최대 개수를 한 줄에 출력한다. 보물을 하나도 분리할 수 없으면 0을 출력한다.

예제4

  1. 예제 1

    입력
    2
2 3
1 3
1 1
1 2 3
2 1 2
3 3
1 3 5
1 1 1
1 2 3
2 1 2
    예상 출력
    1
2

  2. 예제 2

    입력
    1
2 2
0 1000000
0 0
0 1000000
1000000 1000000
    예상 출력
    2

  3. 예제 3

    입력
    1
3 3
0 2 4
0 0 0
1 3 5
0 0 0
    예상 출력
    1

  4. 예제 4

    입력
    4
4 2
0 4 0 4
0 0 4 4
2 100
2 100
4 2
0 1 2 3
0 0 0 0
1 2
1 1
4 2
0 2 4 1
0 0 0 5
6 3
0 1
4 4
300 200 100 200
200 300 200 100
271 129 129 271
271 271 129 129
    예상 출력
    2
4
3
1