seuOJ443 - 折线

题目描述

给定三条折线，请你计算这三条折线与直线 x=0x=0 和 x=nx=n 之间围成区域的面积。

在本题中，我们用一个长度为 n+1n+1 的数组 {An}\{A_n\} 表示一条折线。折线的左端点为 (0,A0)(0,A_0)，右端点为 (n,An)(n,A_n)。折线内部有 n−1n-1 个端点，其坐标分别为 (1,A1),(2,A2),⋯ ,(n−1,An−1)(1,A_1),(2,A_2),\cdots,(n-1,A_{n-1})。特别地，当 n=1n=1 时，折线退化为一条线段。

当 n=3n=3 时，下图即为数组 [1,2,1,2][1,2,1,2] 所表示的折线：

给定三条折线 {An},{Bn},{Cn}\{A_n\},\{B_n\},\{C_n\} 和两条直线 x=0,x=nx=0,x=n。我们称平面上任意一个点 (x,y)(x,y) 被包围，当且仅当点 (x,y)(x,y) 的上方、下方、左侧、右侧有至少一条直线/折线。所有被包围的点所构成的集合，成为这三条折线与直线围成的区域。

现在请你计算该区域的面积。当你所输出的答案与标准答案之间的差的绝对值不超过 10−610^{-6} 时，将被判定为正确。

输入格式

第一行一个正整数 n(1≤n≤100)n(1\le n\le 100)，表示折线段在水平方向的宽度。

接下来 n+1n+1 行，第 ii 行三个正整数 Ai−1,Bi−1,Ci−1(1≤Ai−1,Bi−1,Ci−1≤100)A_{i-1},B_{i-1},C_{i-1}(1\le A_{i-1},B_{i-1},C_{i-1}\le 100)，表示折线 A,B,CA,B,C 的端点 (i−1,Ai−1),(i−1,Bi−1),(i−1,Ci−1)(i-1,A_{i-1}),(i-1,B_{i-1}),(i-1,C_{i-1})。

输出格式

输出一个实数，表示围成区域的面积。你所输出的答案可以保留小数点后任意位，当你的答案与标准答案之间的差的绝对值不超过 10−610^{-6} 时，将被判定为正确。

样例

输入样例 1：

2
1 2 3
2 1 3
1 1 2

输出样例 1：

3.25

样例说明 1：

输入样例 2：

3
4 3 1
1 4 2
3 4 1
3 4 2

输出样例 2：

7.416666666666667

样例说明 2：

输入样例 3：

5
10 37 73
43 15 98
41 4 55
18 4 59
65 92 70
61 66 39

输出样例 3：

239.623336735531865