Under construction

Still being built. Things may change

Archimedes' circles

Time limit1sMemory limit128 MB

Summary
Given N black and M white points, find the maximum number of white points lying inside a circle through some three black points.
Level

Medium7 of 10

Topics
Geometry, Brute force, Math, Combinatorics
Solved
No attempts yet

Problem

Archimedes is remembered for one sentence: "Do not disturb my circles!"

What he was actually working out in the sand is less well known. He drew NN black points and MM white points.

He was trying to solve this problem. Among the circles determined by three black points, which one holds the most white points inside it? A white point counts as inside when it belongs to the disk that the circle bounds.

Young Andro decided to settle this problem, more than 2000 years old. Andro is confused as usual, so he needs your help. Find the largest number of white points that lie inside a single circle passing through three black points.

The picture shows an example whose answer is 33. The circle through AA, BB and CC holds three white points. The circle through AA, BB and DD holds three white points as well. The circle through BB, CC and DD holds one white point. No circle passes through AA, CC and DD.

Input

The first line contains an integer NN (1≤N≤2001 \le N \le 200), the number of black points.

Each of the next NN lines contains the coordinates of one black point, two integers whose absolute values are smaller than 1000010000.

The next line contains an integer MM (1≤M≤2001 \le M \le 200), the number of white points.

Each of the next MM lines contains the coordinates of one white point in the same format.

All points in the input are distinct, and no white point lies on a circle determined by three black points.

Output

Print the largest number of white points inside a single circle determined by three black points. If three black points never determine a circle, print 00.

Examples2

  1. Example 1

    Input
    4
    0 0
    0 2
    2 2
    3 3
    2
    1 1
    100 100
    
    Expected output
    1
    
  2. Example 2

    Input
    4
    4 6
    1 2
    6 2
    8 2
    3
    3 4
    5 5
    100 100
    
    Expected output
    2