#5564. [USACO 2011 Nov] Cow Steeplechase

内存限制:256 MiB 时间限制:5 Sec

题目描述

 给n(n<=250)个线段,这些线段不是水平就是垂直的。坐标范围(1<=xi,yi<=1,000,000,000)

选出尽量多的线段。并且这些线段不相交。线段相交指两个线段存在交点(包括端点)。

输入格式

*第1行:一个整数:N。 
*第2 .. N +1行:第i +1包含四个空格分开的整数,代表一个障碍:Y1_i X1_i,X2_i,Y2_i。 

输出格式

 *第1行:FJ可以选择的最大障碍数目。 

样例

样例输入


			
3
4 5 10 5
6 2 6 12
8 3 8 5
输入详细信息:
有三个可供选择的障碍。第一个是水平段连接(4,5),(10,5),第
二和第三是两条垂直线段(6,2),(6,12),(8,3),(8,5) 。

样例输出


			
2
输出细节:
最佳的方案是选择两个垂直线段(障碍)

数据范围与提示