1729. [BOI2007]修建栅栏

【题目描述】

Leopold真是一个幸运的家伙。他刚刚买彩票中了一笔巨大的房产。这处房产包括一座大厦和一些豪华的楼房，他打算今后住在这里。但是，他的房产并没有能阻止不速之客的栅栏，这让Leopold十分关注。他想要修建一个栅栏，并且为了省钱，他认为栅栏围住大厦就足够了。但除此之外还有一个重要的限制：栅栏不能离任何建筑太近。更精确地，每座建筑都被一个矩形的禁止区域环绕（下文中将其称为‘禁止矩形’），在其中不能修建栅栏。矩形的边与x或y轴平行。栅栏的每一段也必须和x或y轴平行。

帮助Leopold计算能够围住大厦的合法栅栏的最小长度。

图1：大厦（黑色）和三栋其他建筑，周围环绕着禁止矩形。粗黑线画出了围住大厦的最短合法栅栏。

【输入格式】

输入文件的第一行有一个正整数m（1<=m<=100），即建筑物的总数。

接下来m行每行描述了一个禁止矩形。每一行包含四个整数tx,ty,bx,by，其中(tx,ty)是矩形左上角的坐标，(bx,by)是矩形右下角的坐标。坐标满足0<=tx<bx<=10000，以及0<=ty<by<=10000.第一个矩形是大厦的禁止矩形。

【输出格式】

输出一个正整数，即围住大厦的合法栅栏的最短长度。

【样例输入】

4

8 4 13 8

2 1 6 7

4 7 9 11

14 7 19 11

【样例输出】

32

【提示】

对于30%的数据，m<=10.

对于100%的数据，规模如题所示。

【来源】

BOI 2007 Day 2 -- Building a Fence