[USACO11NOV]牛的障碍Cow Steeplechase - 题目 - HelloWorld信息学奥赛题库

题目描述

Farmer John 有个绝妙的主意——举办一场盛大的奶牛跨栏大赛！众所周知，一般的跨栏比赛是让马匹在充满障碍物的赛道上比赛。而 FJ 认为，只要把障碍物做得足够矮，这个比赛同样适用于训练有素的奶牛。

为了设计赛道，FJ 绘制了所有 $N$ 个可能的障碍物摆放的示意图。每个障碍物在二维平面上用一条平行于横轴或纵轴的线段表示。障碍物 $i$ 的端点为 $(X1_i, Y1_i)$ 和 $(X2_i, Y2_i)$。以下是一个示例：

   --+-------   
-----+-----
  ---+---     |
     |     |  |
   --+-----+--+-   |
     |     |  |  | |
     |   --+--+--+-+-
           |  |  | |
              |

约翰希望在满足任意两个障碍物不相交的条件下尽可能多地建造障碍物。以上图为例，最多可以建造 $7$ 个障碍物：

   ----------   
-----------
  -------     |
           |  |
           |  |    |
           |  |  | |
           |  |  | |
           |  |  | |
              |

当两条线段存在任何公共点（包括端点重合）时即视为相交。题目保证初始示意图中任意两条水平线段不会相交，任意两条垂直线段也不会相交。

请帮助 FJ 计算一下他最多能建造多少个障碍物。

输入格式

第 $1$ 行输入一个整数：N。

第 $2\sim N+1$ 行：第 $i+1$ 行包含四个用空格分隔的整数，表示一个障碍物：$X1_i, Y1_i, X2_i$, 和 $Y2_i$。

输出格式

输出一个数，约翰农夫可以选择的最大不相交线段数量。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

【样例解释】

共有三个潜在的障碍物：第一个是连接 $(4,5)$ 到 $(10,5)$ 的水平线段；第二、三个分别是连接 $(6,2)$ 到 $(6,12)$ 和 $(8,3)$ 到 $(8,5)$ 的垂直线段。

【数据范围】

对于 $100\%$ 的数据，$1\le N\le250,1\le X1_i,Y1_i,X2_i,Y2_i\le10^9$。

HelloWorld信息学奥赛题库

少儿编程