#P18814. [Croatian CPC 2026]Kiletovi Krugovi

[Croatian CPC 2026]Kiletovi Krugovi

Kiletovi Krugovi

题目描述

平面上有 NN 个黑点和 MM 个白点。任意三个不共线的黑点都唯一确定一个经过这三个点的圆。

在所有这样确定的圆中,求圆的严格内部所包含的白点数量的最大值。

三个共线的黑点不能确定圆,不予考虑。如果不存在三个不共线的黑点,输出 00。

输入格式

第一行包含整数 NN(1≤N≤2001\le N\le200),表示黑点数量。

接下来 NN 行,每行包含两个整数 xi,yix_i,y_i(−10000<xi,yi<10000-10000<x_i,y_i<10000),表示一个黑点的坐标。

接下来一行包含整数 MM(1≤M≤2001\le M\le200),表示白点数量。

接下来 MM 行,每行包含两个整数 ui,viu_i,v_i(−10000<ui,vi<10000-10000<u_i,v_i<10000),表示一个白点的坐标。

保证全部 N+MN+M 个点互不相同。保证任意一个白点都不在任意三个不共线黑点所确定的圆周上。

输出格式

输出一个整数,表示某个合法圆内部最多能够包含的白点数量。如果没有合法的圆,输出 00。

样例 1

输入

4
0 0
0 2
2 2
3 3
2
1 1
100 100

输出

1

样例 2

输入

4
4 6
1 2
6 2
8 2
3
3 4
5 5
100 100

输出

2