UOJ Logo 蜗牛编程训练题库

JZOJ

#1128. 【usaco2019FEB_silver_T2】Painting The Barn

Statistics
时间限制:1s    空间限制:256MB    输入文件:paintbarn.in    输出文件:paintbarn.out
当前24小时内您还剩30次提交本题的机会

题目描述

农夫约翰不擅长多任务处理。他经常分心,很难完成长的项目。目前,他正试图在谷仓的一侧上漆,但他一直在画小矩形区域,然后由于照料奶牛的需要而偏离了方向,使得谷仓的某些部分上漆的涂料比其他部分多。

我们可以将谷仓的一侧描述为一个二维x-y平面,农夫约翰在该平面上绘制n个矩形,每个矩形的边都与坐标轴平行,每个矩形由谷仓的左下角和右上角点的坐标描述。

农夫约翰想在谷仓上涂几层油漆,这样在不久的将来就不需要再重新粉刷了。但是,他不想浪费时间涂太多的油漆。结果表明,K涂层是最佳用量。请在他画完所有的长方形后,帮他确定谷仓有多少面积被K层油漆覆盖。

输入格式

输入的第一行包含n和k(1≤k≤n≤100000)。

其余n行中的每一行包含四个整数x1、y1、x2、y2,描述正在绘制的矩形区域,左下角(x1、y1)和右上角(x2、y2)。所有x和y值都在0…1000范围内,并且所有矩形都有正面积。

输出格式

请输出谷仓被K层油漆覆盖的区域。

样例数据

input

3 2
1 1 5 5
4 4 7 6
3 3 8 7

output

8

数据规模与约定

时间限制:$1 \text {s}$

空间限制:$256 \text {MB}$

Solutions

标题 发表者 发表日期
None