1 人解决，4 人已尝试。
1 份提交通过，共有 34 份提交。
9.9 EMB 奖励。
2375. Building a Fence
单点时限: 10.0 sec
内存限制: 256 MB
Leopold is indeed a lucky fellow. He just won a huge estate in the lottery. The estate contains several grand buildings in addition to the main mansion, in which he intends to live from now on. However, the estate lacks a fence protecting the premises from trespassers, which concerns Leopold to a great extent. He wants to build a fence and, in order to save money, he decides it is sufficient to have a fence that encloses the main mansion, except for one important restriction: the fence must not lie too close to any of the buildings. To be precise, seen from above, each building is enclosed in a surrounding forbidden rectangle within which no part of the fence may lie. The rectangles’ sides are
parallel to the x- and y-axis. Each part of the fence must also be parallel either to the x-axis or the y-axis.
Help Leopold to compute the minimum length of any allowed fence enclosing the main mansion.
Figure 1: The main mansion (black) and three other buildings with surrounding forbidden rectangles. The thick black line shows a shortest allowed fence enclosing the main mansion.
输入格式
The first line of the input file contains a positive integer m (1 ≤m ≤100), the number of buildings of the estate. Then follow m lines each describing a forbidden rectangle enclosing a building. Each row contains four space-separated integers tx, ty, bx, and by, where (tx, ty) are the coordinates of the upper left corner and (bx, by) the coordinates of the bottom right corner of the rectangle. All coordinates obey 0 ≤tx < bx ≤10,000 and 0 ≤ty < by ≤ 10,000. The first rectangle is the forbidden rectangle enclosing the main mansion.
输出格式
It contains one line with a single positive integer equal to the minimum length of any allowed fence enclosing the main mansion.
样例
Input
4 8 4 13 8 2 1 6 7 4 7 9 11 14 7 19 11
Output
32
题目标签