本资源提供北京大学ACM竞赛题库及其参考解答的打包下载服务,涵盖多种编程挑战题目与详细解析。适合编程爱好者和参赛选手使用。
解题报告:Fence题目来源:POJ 1031
解法或类型:计算几何
作者:杨清玄
**问题描述**
在一片平坦的草地上,有一段围栏将其包围起来形成一个封闭区域。该围栏的高度为h,在平面投影中表现为一条无自交点的闭合多边形线,由N个顶点的笛卡尔坐标(Xi, Yi)确定。在原点(0, 0)处放置了一个灯泡。这个灯可以位于围栏内外任何位置,但不能处于围栏边界上。
问题的关键在于计算该围栏受到灯光照射后的总照度。已知公式为:
I0=k/r
其中k是一个与具体地点无关的常数值,r是平面投影中任意一点到光源的距离。
对于一个无限小、宽度为dl的高度h的垂直板,其受光强度dI可表示为:
dI=I0*|cosα|*dl*h
这里 I0 是该围栏某点处的光照强度,α是在平面投影中从围栏边缘法线方向到光源的方向所成的角度。
**解题思路**
此问题属于计算几何类型。根据题目给出的信息,可以推导出dI=I0*|cosα|*dl*h
这意味着一条边上的总照度为:
a*h*k = ∫ I0 * |cos(α)| dl
其中下标表示积分的范围是从X1到X2。
因此实际上需要计算整个围栏相对于原点所张开的角度,定义FENCE是一个有向闭合回路。每条边都是有方向性的:如果按照边的方向对原点所张开的角度是顺时针,则该角度为正;如果是逆时针则为负。
对于包含原点的区域,总计算值应接近±2π(以弧度表示);
对于不包括原点的情况,在整个过程中保持的最大与最小角之差就是围栏对光源所张开的角度。如果这个角度超过2π,则取2π作为结果。
数据结构:使用POINT数组存储每个顶点的位置
时空分析:
如果有N个顶点,空间复杂度为O(N),时间复杂度也为O(N)。
源程序:fence.cpp