#P18846. [Croatian CPC2022] Hrabro Hvalisanje

[Croatian CPC2022] Hrabro Hvalisanje

Hrabro Hvalisanje

题目描述

Mirko 和 Slavko 正在劈柴。他们争论一次挥动斧头最多能够碰到多少根木柴。你想用实际行动向他们展示答案。

把每根木柴看作一个边平行于坐标轴的闭矩形,把斧头看作一条长度为 ll 的线段。线段的位置和方向可以任意选择。

求一条长度为 ll 的线段最多能够与多少个给定矩形有非空交集。只接触矩形的边或顶点,也算相交。

输入格式

第一行包含两个整数 n,ln,l,分别表示矩形数量和线段长度。

接下来 nn 行,每行包含四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,分别表示一个矩形左下角和右上角的坐标。

输出格式

输出一个整数,表示所求的最大相交矩形数量。

数据范围

  • 1≤n≤151\le n\le15;
  • 1≤l≤10001\le l\le1000;
  • 0≤x1≤x2≤10000\le x_1\le x_2\le1000;
  • 0≤y1≤y2≤10000\le y_1\le y_2\le1000。

矩形可以退化为线段或点。

样例 1

输入

4 3
0 0 1 1
2 0 3 1
4 0 5 1
6 0 7 1

输出

3

样例解释

样例中的线段与矩形