만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

아르키메데스의 원

시간 제한1초메모리 제한128 MB

요약
검은 점 N개와 흰 점 M개가 주어질 때, 검은 점 세 개를 지나는 원 안에 들어가는 흰 점 개수의 최댓값을 구한다.
난이도

보통10점 중 7점

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

문제

아르키메데스가 남긴 말은 널리 알려져 있다. "내 원을 건드리지 마라!"

모래 위에서 그가 실제로 무엇을 풀고 있었는지는 덜 알려져 있다. 그는 검은 점 NN개와 흰 점 MM개를 그렸다.

그가 풀려던 문제는 이렇다. 검은 점 세 개로 결정되는 원 가운데 내부에 흰 점을 가장 많이 담는 원은 어느 것인가? 흰 점이 그 원으로 둘러싸인 원판에 속하면 그 점은 원 안에 있다고 본다.

젊은 안드로는 2000년이 넘은 이 문제를 풀기로 했다. 안드로는 늘 그렇듯 헷갈려 하니 도와주자. 검은 점 세 개를 꼭짓점으로 하는 삼각형의 외접원 하나가 담는 흰 점 개수의 최댓값을 구하면 된다.

그림은 답이 33인 예다. 점 AA, BB, CC가 정하는 원은 흰 점 세 개를 담는다. 원 AA, BB, DD도 흰 점 세 개를 담는다. 원 BB, CC, DD는 흰 점 한 개를 담는다. AA, CC, DD를 지나는 원은 없다.

입력

첫 줄에 검은 점의 개수 NN (1≤N≤2001 \le N \le 200)이 주어진다.

다음 NN개 줄에는 검은 점의 좌표가 한 줄에 하나씩 주어진다. 각 줄은 절댓값이 1000010000보다 작은 정수 두 개다.

그다음 줄에 흰 점의 개수 MM (1≤M≤2001 \le M \le 200)이 주어진다.

다음 MM개 줄에는 흰 점의 좌표가 같은 형식으로 주어진다.

입력의 모든 점은 서로 다르고, 검은 점 세 개로 결정되는 어떤 원 위에도 흰 점이 놓이지 않는다.

출력

검은 점 세 개로 결정되는 원 하나가 내부에 담는 흰 점 개수의 최댓값을 첫 줄에 출력한다. 검은 점 세 개로 원을 만들 수 없으면 00을 출력한다.

예제2

  1. 예제 1

    입력
    4
    0 0
    0 2
    2 2
    3 3
    2
    1 1
    100 100
    
    예상 출력
    1
    
  2. 예제 2

    입력
    4
    4 6
    1 2
    6 2
    8 2
    3
    3 4
    5 5
    100 100
    
    예상 출력
    2