#1009. 「USACO 2011.11 Gold」Cow Steeplechase

内存限制
512 MiB
时间限制
2000 ms
文件输入输出
steeple.in ≫ steeple.out
题目类型
传统
评测方式
文本比较
上传者 admin
题目来源 usaco

显示标签

题目描述

给定 条平行于坐标轴的线段,或垂直或水平,每条线段可以用两个端点 表示。垂直的与垂直的,水平的与水平的线段之间保证没有交点。

要求选出尽量多的线段使得这些线段两两没有交点(顶点也算)。输出最多能选出多少条线段。

输入格式 steeple.in

第一行包含一个整数

接下来 行,每行包含四个整数 ,表示一条与坐标轴平行的线段。

输出格式 steeple.out

第一行包含一个整数表示最多能选出两两无交的线段数量。

样例

输入

3 
4 5 10 5 
6 2 6 12 
8 3 8 5

输出

2

解释

最优解是选择两条垂直的线段。

数据范围与提示