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$。