bzoj#P2509. [2011福建集训] 送分题

[2011福建集训] 送分题

题目描述

给出平面上的 MM 条平行于坐标轴的线段,问有多少个正方形。

输入格式

11 行为两个正整数 NMN,M 。 接下来 MM行,每行 44 个非负整数 $x_{1},y_{1},x_{2},y_{2}(0 \le x_{1} \le x_{2} \le N,0 \le y_{1}\le y_{2} \le N)$ ,描述了线段的两个端点。

输出格式

仅包括一个正整数,为平面上正方形的个数。

3 8
0 0 0 3
1 0 1 3
2 0 2 2
3 0 3 3
0 0 3 0
0 1 3 1
0 2 3 2
0 3 3 3
11

提示

样例对应了如下一张图: 其中边长为 11 的正方形有 77 个,边长为 22 的正方形有 33 个,边长为 33 的正方形有 11个。

所以答案为 7+3+1=117+3+1=11

数据规模

对于 20%20\% 的数据,有 N30N\le30

对于 40%40\% 的数据,有 N100N\le100

对于 60%60\% 的数据,有 N800N\le800

对于 100%100\% 的数据,有 N1000M400000N\le1000,M\le400000 ,并保证任意两条线段没有重合部分。

题目来源

2011福建集训