← 返回题目
题库练习 疯狂的篱笆
← 上一题 下一题 →

A2198 | 疯狂的篱笆

来源USACO / 2012
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

在访问了一个现代美术馆后，约翰农夫决定移动n个在他的牧场之间的栅栏来

重新设计他的农场。每个栅栏用一个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 范围内的整数。

输出格式

* 第 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
C++ 编辑器
输入
输出