P3061 [USACO12DEC] Crazy Fences S
题目描述
在访问了一个现代美术馆后,约翰农夫决定移动 $N$ 个在他的牧场之间的栅栏来
重新设计他的农场。每个栅栏用一个 2D 平面的线段来描述。两个栅栏只有在他们的端点才会相遇。每个栅栏在两个端点接触其他的两个栅栏。
约翰农夫有 $C$ 头牛在他的农场。每头牛住在 2D 平面的不在任何栅栏的一个点,并且没有两头牛在同一个点。如果两头牛可以不接触任何栅栏地走到一起,他们就是在同一个社区。请确定最大的社区的牛的数量。
输入格式
第一行包含两个整数 $N$ 和 $C$。
接下来 $N$ 行,每行包含四个整数 $x_1,y_1,x_2,y_2$,表示一个栅栏的两个端点为 $(x_1,y_1)$ 和 $(x_2,y_2)$。所有坐标都是 $0...1,000,000$ 范围内的整数。
接下来 $C$ 行,每行包含两个整数 $x,y$,表示一头牛的所在位置为 $(x,y)$。所有坐标都是 $0...1,000,000$ 范围内的整数。
输出格式
输出最大社区的牛的数量。
说明/提示
奶牛 $2$ 和 $4$ 在一个社区中。
奶牛 $1$ 和 $3$ 各自在一个社区中。
最大社区的牛的数量为 $2$。