UVa 667 Fence-开发者社区

题目描述

在平坦的场地上有一片由栅栏围成的区域。栅栏高度为hhh，其平面投影是一条封闭的、不自交的折线，由NNN个顶点的笛卡尔坐标(Xi,Yi)(X_i, Y_i)(Xi,Yi)给出。在场地上的点(0,0)(0, 0)(0,0)处放置了一盏灯。灯可能在栅栏内部或外部，但绝不会在栅栏边上。

栅栏是理想黑色的，既不反射、不散射，也不透光。研究表明，照射到栅栏上任意被照亮点的光强满足：

I0=kr I_0 = \frac{k}{r}I0=rk

其中kkk是已知常数，rrr是该点与灯在平面投影上的距离。一小段宽度为dldldl、高度为hhh的竖直窄板的照度为：

dI=I0⋅∣cos⁡a∣⋅dl⋅h dI = I_0 \cdot |\cos a| \cdot dl \cdot hdI=I0⋅∣cosa∣⋅dl⋅h

其中aaa是该点处栅栏边的法线与指向灯的方向之间的夹角。

请编写程序，计算栅栏的总照度，定义为所有被照亮的栅栏板的照度之和。

输入格式

第一行为整数MMM，然后是一个空行，接着是MMM组数据集。数据集之间有一个空行。

每组数据集第一行包含三个实数kkk、hhh和整数NNN（3≤N≤1003 \le N \le 1003≤N≤100），用空格分隔。随后NNN行，每行两个实数XiX_iXi、YiY_iYi，表示顶点的坐标。

输出格式

对于每组数据集，输出总照度，四舍五入保留两位小数。
数据集之间打印一个空行。

样例

输入

2 0.5 1.7 3 1.0 3.0 2.0 - 1.0 -4.0 -1.0 1.5 10.0 4 0.0 -3.0 3.5 2.0 0.0 4.0 1.0 0.0

输出

5.34 47.12

题目分析

本题的核心是计算栅栏接收到的总光照。栅栏由若干条线段组成，每条线段上的每一个点都可能被灯照亮，但若灯在栅栏外部，部分线段可能被其他线段遮挡，未被照亮的部分不应计入。

直接对每条线段的每一点进行积分是复杂的，但可以通过几何关系将照度积分转化为角度的累加。

设栅栏上某一小段的长度为dldldl，它与灯的距离为rrr，法线与灯方向夹角的余弦绝对值为∣cos⁡a∣|\cos a|∣cosa∣。该小段对灯所张的微小角度dθd\thetadθ满足：

dθ=∣cos⁡a∣⋅dlr d\theta = \frac{|\cos a| \cdot dl}{r}dθ=r∣cosa∣⋅dl

这是因为∣cos⁡a∣⋅dl|\cos a| \cdot dl∣cosa∣⋅dl是该小段在垂直于视线方向上的投影长度，除以半径rrr即得所张角度。于是该小段的照度微元可以写成：

dI=kr⋅∣cos⁡a∣⋅dl⋅h=k⋅h⋅dθ dI = \frac{k}{r} \cdot |\cos a| \cdot dl \cdot h = k \cdot h \cdot d\thetadI=rk⋅∣cosa∣⋅dl⋅h=k⋅h⋅dθ

因此，任意一段被照亮的栅栏的照度等于k⋅hk \cdot hk⋅h乘以该段在灯处所张的总角度。

这样，问题转化为：计算多边形栅栏上所有被照亮部分在原点（灯）处所张的角度之和。

若灯在栅栏内部，则每个方向都能照射到栅栏，总角度为2π2\pi2π，总照度为kh⋅2πk h \cdot 2\pikh⋅2π。
若灯在外部，则栅栏整体在灯处投影为一个连续的角度区间（因为多边形是简单闭曲线，其投影到单位圆上是连通的），该区间的长度即为所有照亮方向的总角度。

解题思路

每条边贡献的角度区间

对于一条边，其两个端点分别为AAA和BBB。计算它们相对于原点的极角θA=atan2(Ay,Ax)\theta_A = \text{atan2}(A_y, A_x)θA=atan2(Ay,Ax)和θB=atan2(By,Bx)\theta_B = \text{atan2}(B_y, B_x)θB=atan2(By,Bx)，并将它们归一化到[0,2π)[0, 2\pi)[0,2π)。

从θA\theta_AθA逆时针转到θB\theta_BθB的夹角差为：

Δ=(θB−θA) mod 2π \Delta = (\theta_B - \theta_A) \bmod 2\piΔ=(θB−θA)mod2π

由于线段不经过原点（灯不在边上），线段所张的角度必小于π\piπ。如果Δ>π\Delta > \piΔ>π，则说明实际张角是另一侧较小的那部分，此时应交换AAA和BBB，并令Δ=2π−Δ\Delta = 2\pi - \DeltaΔ=2π−Δ。

于是该边贡献的角度区间为[θA,θA+Δ][\theta_A, \theta_A + \Delta][θA,θA+Δ]。若该区间超出2π2\pi2π，则将其拆分为[θA,2π)[\theta_A, 2\pi)[θA,2π)和[0,θA+Δ−2π][0, \theta_A + \Delta - 2\pi][0,θA+Δ−2π]两个区间。

合并区间得到总视角

将所有边贡献的区间收集起来，按左端点排序，然后进行区间合并。合并后的总长度SSS即为栅栏在原点处可见的总角度。

对于灯在内部的情况，合并后的SSS会接近2π2\pi2π，此时可以直接令S=2πS = 2\piS=2π以避免浮点误差。

最终答案即为：

answer=k⋅h⋅S \textit{answer} = k \cdot h \cdot Sanswer=k⋅h⋅S

输出时保留两位小数。

算法复杂度

每条边产生至多两个区间，共有O(N)O(N)O(N)个区间。排序合并的复杂度为O(Nlog⁡N)O(N \log N)O(NlogN)，N≤100N \le 100N≤100，完全可行。

代码实现

// Fence// UVa ID: 667// Verdict: Accepted// Submission Date: 2026-07-02// UVa Run Time: 0.000s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constdoublePI=acos(-1.0);constdoubleTWO_PI=2.0*PI;constdoubleEPS=1e-12;structPoint{doublex,y;};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intM;cin>>M;for(intds=0;ds<M;++ds){doublek,h;intN;cin>>k>>h>>N;vector<Point>pts(N);for(inti=0;i<N;++i)cin>>pts[i].x>>pts[i].y;vector<pair<double,double>>intervals;for(inti=0;i<N;++i){intj=(i+1)%N;doubletheta1=atan2(pts[i].y,pts[i].x);doubletheta2=atan2(pts[j].y,pts[j].x);if(theta1<0)theta1+=TWO_PI;if(theta2<0)theta2+=TWO_PI;doublediff=theta2-theta1;if(diff<0)diff+=TWO_PI;// 线段张角小于 πif(diff>PI){swap(theta1,theta2);diff=TWO_PI-diff;}doublestart=theta1;doubleend=theta1+diff;if(end<=TWO_PI+EPS){intervals.push_back({start,min(end,TWO_PI)});}else{intervals.push_back({start,TWO_PI});intervals.push_back({0.0,end-TWO_PI});}}// 合并区间sort(intervals.begin(),intervals.end());doubletotal=0.0;doublecurL=-1.0,curR=-1.0;for(auto&iv:intervals){doublel=iv.first,r=iv.second;if(curL<0){curL=l;curR=r;}elseif(l<=curR+EPS){curR=max(curR,r);}else{total+=curR-curL;curL=l;curR=r;}}if(curL>=0)total+=curR-curL;if(TWO_PI-total<EPS)total=TWO_PI;doubleans=k*h*total;cout<<fixed<<setprecision(2)<<ans;if(ds<M-1)cout<<"\n\n";elsecout<<"\n";}return0;}