华师一附中OI组

标题: 城市的地平线 [打印本页]

作者: admin 时间: 2018-5-13 00:58
标题: 城市的地平线
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.

欢迎光临华师一附中OI组 (http://hsyit.cn/)