A2198. 疯狂的篱笆
编程题
省选/NOI-
知识点
题目描述
在访问了一个现代美术馆后，约翰农夫决定移动n个在他的牧场之间的栅栏来
重新设计他的农场。每个栅栏用一个2D平面的线段来描述。两个栅栏只有在他们的端点才会相遇。每个栅栏在两个端点接触其他的两个栅栏。
约翰农夫有c头牛在他的农场。每头牛住在2D平面的不在任何栅栏的一个点，并且没有两头牛在同一个点。如果两头牛可以不接触任何栅栏地走到一起，他们就是在同一个社区。请确定最大的社区的牛的数量。
重新设计他的农场。每个栅栏用一个2D平面的线段来描述。两个栅栏只有在他们的端点才会相遇。每个栅栏在两个端点接触其他的两个栅栏。
约翰农夫有c头牛在他的农场。每头牛住在2D平面的不在任何栅栏的一个点，并且没有两头牛在同一个点。如果两头牛可以不接触任何栅栏地走到一起，他们就是在同一个社区。请确定最大的社区的牛的数量。
输入格式
* 第 1 行：两个空格分隔的整数 N 和 C。
* 第 2..1+N 行：每行包含四个整数：x1、y1、x2、y2，表示从点 （x1，y1） 到点 （x2，y2） 的栅栏。所有坐标都是 0..1,000,000 范围内的整数。
* 第 2+N 行。1+N+C：每行包含两个整数 x 和 y，分别描述一头奶牛的位置。所有坐标都是 0..1,000,000 范围内的整数。
* 第 2..1+N 行：每行包含四个整数：x1、y1、x2、y2，表示从点 （x1，y1） 到点 （x2，y2） 的栅栏。所有坐标都是 0..1,000,000 范围内的整数。
* 第 2+N 行。1+N+C：每行包含两个整数 x 和 y，分别描述一头奶牛的位置。所有坐标都是 0..1,000,000 范围内的整数。
输出格式
* 第 1 行：最大社区的奶牛数量。
输入输出样例
输入 #1
10 4 0 0 10 0 10 0 10 10 0 0 0 10 10 10 0 10 8 8 9 8 9 8 8 9 8 9 8 8 2 7 3 2 3 2 7 5 7 5 2 7 15 3 1 4 4 5 7 1
输出 #1
2
说明/提示
有 10 个栅栏和 4 头奶牛。栅栏形成一个包含两个三角形的正方形。
奶牛 #2 和 #4 属于同一个社区。奶牛 #1 和 #3 都是 1 号奶牛社区的成员。
奶牛 #2 和 #4 属于同一个社区。奶牛 #1 和 #3 都是 1 号奶牛社区的成员。