#P18846. [Croatian CPC2022] Hrabro Hvalisanje
[Croatian CPC2022] Hrabro Hvalisanje
Hrabro Hvalisanje
题目描述
Mirko 和 Slavko 正在劈柴。他们争论一次挥动斧头最多能够碰到多少根木柴。你想用实际行动向他们展示答案。
把每根木柴看作一个边平行于坐标轴的闭矩形,把斧头看作一条长度为 的线段。线段的位置和方向可以任意选择。
求一条长度为 的线段最多能够与多少个给定矩形有非空交集。只接触矩形的边或顶点,也算相交。
输入格式
第一行包含两个整数 ,分别表示矩形数量和线段长度。
接下来 行,每行包含四个整数 ,分别表示一个矩形左下角和右上角的坐标。
输出格式
输出一个整数,表示所求的最大相交矩形数量。
数据范围
- ;
- ;
- ;
- 。
矩形可以退化为线段或点。
样例 1
输入
4 3
0 0 1 1
2 0 3 1
4 0 5 1
6 0 7 1
输出
3
样例解释
