HihoCoder1642 : 三角形面积和([Offer收割]编程练习赛37)(求面积)(扫描线||暴力)(占位)

描述

如下图所示,在X轴上方一共有N个等腰直角三角形。这些三角形的斜边与X轴重合,斜边的对顶点坐标是(Xi, Yi)。

             (11,5)
      (4,4)    /
        /(7,3)  
       /  //    
      /   //     
     /   / /      
------------------------->

你能求出这些三角形覆盖的面积之和吗? (重叠部分只算一次)

输入

第一行包含一个整数N。  

以下N行每行包含两个整数(Xi, Yi),代表第i个三角形顶点的坐标。

对于30%的数据,1 ≤ N ≤ 100, 0 ≤ Xi, Yi ≤ 100  

对于100%的数据,1 ≤ N ≤ 100000,0 ≤ Xi, Yi ≤ 100000

输出

覆盖的面积,保留2位小数。

样例输入

3   
7 3
4 4  
11 5

样例输出

42.00
原文地址:https://www.cnblogs.com/hua-dong/p/8133941.html