/ Vijos / 题库 /

正方形计数

正方形计数

背景

与Orz4-4类似

描述

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

格式

输入格式

输入的第1行为两个正整数n,m,接下来m行,每行4个非负整数x1,y1,x2,y2(0≤x1≤x2≤n,0≤y1≤y2≤n),描述了线段的两个端点。

输出格式

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

样例1

样例输入1

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

样例输出1

11

限制

对于20%的数据,有n≤30;
对于40%的数据,有n≤100;
对于60%的数据,有n≤800;
对于100%的数据,有n≤1000,m≤400000,并保证任意两条线段没有长度大于0的重合部分。

时限1s

提示

边长为1的正方形有7个,边长为2的正方形有3个,边长为3的正方形有1个。

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

信息

ID
1631
难度
7
分类
数据结构 | 树状数组 点击显示
标签
(无)
递交数
190
已通过
35
通过率
18%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库