#P1882. Pku2150 Crossing Prisms

    ID: 904 传统题 1000ms 512MiB 尝试: 8 已通过: 3 难度: 7 上传者: 标签>CF2300提高+/省选-扫描线分段线性函数精确积分同向双指针容斥原理Japan2004

Pku2150 Crossing Prisms

题目描述

给出一个简单多边形的截面 SS,其坐标是 (a,b)(a,b)。用它构造两个直棱柱。

  • 第一个棱柱由所有 (x,a,b)(x,a,b) 构成,其中 0≤x≤100\le x\le10、(a,b)∈S(a,b)\in S。
  • 第二个棱柱由所有 (a,y,b)(a,y,b) 构成,其中 0≤y≤100\le y\le10、(a,b)∈S(a,b)\in S。

求两个棱柱交集的表面积。

输入格式

输入包含多组数据。每组第一行一个整数 nn(3≤n≤43\le n\le4),随后 nn 行,每行两个整数 ai,bia_i,b_i(0≤ai,bi≤100\le a_i,b_i\le10),表示截面多边形的顶点。顶点按顺时针顺序给出,末点与首点连边。多边形的边界不自交,也不自接触。读到单独一行 0 时结束。

输出格式

对每组数据输出一行表面积。答案的绝对误差不得超过 10−410^{-4}。小数位数不限。

样例

4
5 0
0 10
7 5
10 5
4
7 5
10 5
5 0
0 10
4
0 10
10 10
10 0
0 0
3
0 0
0 10
10 0
4
0 10
10 5
0 0
9 5
4
5 0
0 10
5 5
10 10
4
0 5
5 10
10 5
5 0
4
7 1
4 1
0 1
9 5
0
194.8255
194.8255
600.0000
341.4214
42.9519
182.5141
282.8427
149.2470

ICPC 2004 爱媛赛站组委会原题 I