做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 1461. -- 切分矩形组

1461: 切分矩形组

时间限制: 1 Sec  内存限制: 128 MB
提交: 66  解决: 11
[上一题][提交][讨论版][状态][下一题]

题目描述

给定若干个平行于坐标轴的互不重叠的矩形,矩形的顶点都是整点。要求画一根平行于y轴的直线x=k(k是整数) ,使得这些矩形落在直线两边面积之差最小。

注意:若直线穿过一个矩形,将会把它切成两个部分,分属左右两侧。

输入

第一行是整数n,表示有n个矩形(0 < n <= 100000)。

接下来是n行,每行表示一个矩形。每行有4个整数left,top,w,h 分别代表矩形左上角横坐标,矩形左上角纵坐标,矩形宽度,矩形高度。

0 <= left,top <= 1000000, 0 <= w,h <= 100000。

输出

输出使得直线 x= k 两边所包含的矩形面积差最小的k。如果有多条直线满足要求,输出最小的k。

样例输入

2
1 1 100 100
1000 1 100 100

样例输出

101

提示

本题数据疑有误,发现问题请联系管理员。

标签

[上一题][提交][讨论版][状态][下一题]