城市的地平线

admin

http://poj.org/problem?id=3277
【题目描述】远望城市的地平线，地平线上竖立着一些矩形的建筑物，现在要求知道这些矩形的覆盖面积（会有重叠面积，单不重复算，只算所有建筑物轮廓覆盖的面积）。
所有矩形的下边与地平线重叠。现在有N个矩形，每个矩形给出 左边X坐标Ai和右边的X坐标Bi，和上边的Y坐标Hi（下边的Y坐标就是0）
【范围】1 ≤ N ≤ 40,000 ,      1 ≤ Ai < Bi ≤ 1,000,000,000,      1 ≤ Hi ≤ 1,000,000,000
【输入格式】
    第一行 N ，下来N行，每行三个整数 Ai, Bi, and Hi
【输出格式】
    一个整数，整个建筑群的轮廓覆盖的总面积。
Sample Input
4
2 5 1
9 10 4
6 8 2
4 6 3
Sample Output
16
提示：3*1 + 1*4 + 2*2 + 2*3 - 1 = 16.