New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

1873: 跨栏比赛

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：1 通过：1
提交提交记录统计

题目描述

农民约翰有一个想法，创造一项新的观赛运动：牛跨栏比赛！
为了设计他的赛道，约翰制作了一张包含 N 个障碍物的地图。
每个障碍物在二维平面上用与水平或垂直轴平行的线段表示。
障碍物 i 的两个端点为 ( X1_i , Y1_i ) 和 ( X2_i , Y2_i )。
下面是一个例子： 
   --+-------   
-----+-----
  ---+---     |
     |     |  |
   --+-----+--+-   |
     |     |  |  | |
     |   --+--+--+-+-
           |  |  | |
              |
但是上图中存在障碍物之间相交的情况。
比赛要求所有障碍物都不相交，因此需要将障碍物去除一部分。
农夫希望尽可能保留障碍物，上述例子最多可以保留7个障碍物： 
   ----------   
-----------
  -------     |
           |  |
           |  |    |
           |  |  | |
           |  |  | |
           |  |  | |
              |
两条线段相交定义为：两条线段存在公共点，即使公共点是端点也视为相交。
现在给定 N 条线段，每条线段为水平线段或者垂直线段。
输入保证的水平线段之间不会相交，垂直线段之间不会相交。
请求最多能保留多少根线段使它们互不相交。

输入格式

输入第一行为正整数 N ，1 <= N <= 250。
接下来 N 行，每行四个整数表示第 i 条线段的端点：X1_i、Y1_i、X2_i、Y2_i。
1 <= X1_i, Y1_i, X2_i, Y2_i <= 1,000,000,000。

输出格式

输出一个数字表示答案。

输入样例 复制 

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

输出样例 复制 

2

数据范围与提示

来源：USACO 2011.11