UVa 10641 Barisal Stadium

题目描述

孟加拉板球控制委员会决定在巴里萨尔建造一座新的国际板球场。该体育场形状为凸多边形，需要在外部安装泛光灯以便在灯光下比赛。每个泛光灯可以照亮体育场的某些边，建造每个灯需要一定成本。

照亮条件：一条边被某个灯照亮，当且仅当该边的外法向量与从灯到该边某点的光线向量之间的夹角为锐角。

输入格式：

• 每个测试用例以一个整数NNN开始，表示凸多边形的边数（3≤N≤303 \le N \le 303≤N≤30）。
• 接下来NNN行按逆时针顺序给出多边形顶点的坐标。
• 然后是一个整数MMM（1≤M≤10001 \le M \le 10001≤M≤1000），表示可选灯的位置数量。
• 接下来MMM行，每行包含三个整数x,y,cx, y, cx,y,c，表示灯的位置坐标(x,y)(x, y)(x,y)和建造成本ccc。所有灯的位置都在多边形外部。

输入以N=0N = 0N=0结束。

输出格式：对于每个测试用例，输出完全照亮所有边的最小成本。如果不可能完全照亮，输出Impossible.。

题目分析

本题要求选择一组灯，使得凸多边形的所有边都被至少一盏灯照亮，且总成本最小。这是一个几何覆盖问题与组合优化问题的结合。

关键难点

1. 几何判断：如何判断一盏灯能否照亮某条边？
2. 覆盖性质：对于凸多边形，一盏灯能照亮的边具有什么特征？
3. 环形结构：多边形是闭合的，如何正确处理首尾相连的情况？
4. 优化选择：如何在众多灯中选择最小成本的组合？

解题思路

1. 几何判断条件

对于一条边ABABAB（从顶点AAA到BBB，按逆时针顺序）：

• 边向量：AB⃗=B−A\vec{AB} = B - AAB=B−A
• 外法向量：将AB⃗\vec{AB}AB顺时针旋转90∘90^\circ90∘，得到n⃗=(ABy,−ABx)\vec{n} = (AB_y, -AB_x)n=(ABy​,−ABx​)
• 灯LLL到顶点AAA的向量：v⃗=L−A\vec{v} = L - Av=L−A
• 照亮条件：n⃗⋅v⃗>0\vec{n} \cdot \vec{v} > 0n⋅v>0，即点积为正，表示两向量夹角为锐角。

注意：为什么用顺时针旋转而不是逆时针？因为题目中给出的条件是“外法向量”，对于逆时针排列的多边形，外法向量实际上是顺时针旋转得到的。

2. 重要观察：连续覆盖性

对于凸多边形，一盏灯能照亮的边是连续的一段。原因：

• 外法向量沿多边形边界连续变化
• 照亮条件（点积>0>0>0）是连续的
• 因此，如果一盏灯能照亮边iii和边jjj（i<ji < ji<j），那么它一定能照亮所有iii到jjj之间的边

这个性质将问题转化为区间覆盖问题。

3. 区间表示与处理

将多边形的NNN条边编号为000到N−1N-1N−1。对于每盏灯，找出它能照亮的最长连续边段[L,R][L, R][L,R]。由于多边形是环形的，可能出现L>RL > RL>R的情况（即跨越N−1N-1N−1到000）。处理方法：

• 如果L≤RL \le RL≤R，区间为[L,R][L, R][L,R]
• 如果L>RL > RL>R，将其转换为[L,R+N][L, R+N][L,R+N]，其中右端点加NNN使其连续

4. 动态规划求解

定义dp[i][j]dp[i][j]dp[i][j]表示从顶点iii开始，覆盖到顶点jjj（包含）的所有边的最小成本。这里iii和jjj的取值范围可以扩展到[0,2N−1][0, 2N-1][0,2N−1]，以处理环形。

状态转移：
对于每个灯的覆盖区间[l,r][l, r][l,r]及其成本ccc：

• 如果已经覆盖到lll（即dp[i][l]dp[i][l]dp[i][l]已知）
• 那么可以选择这盏灯，将覆盖范围扩展到l+1,l+2,…,rl+1, l+2, \ldots, rl+1,l+2,…,r
• 更新：dp[i][j]=min⁡(dp[i][j],dp[i][l]+c)dp[i][j] = \min(dp[i][j], dp[i][l] + c)dp[i][j]=min(dp[i][j],dp[i][l]+c)，其中j∈[l+1,r]j \in [l+1, r]j∈[l+1,r]

初始化：

• dp[i][i]=0dp[i][i] = 0dp[i][i]=0（从iii开始，覆盖到iii的成本为000，表示还没覆盖任何边）

环形处理：
由于我们复制了区间（将[l,r][l, r][l,r]也复制为[l+N,r+N][l+N, r+N][l+N,r+N]），最终答案应从所有dp[i][j]dp[i][j]dp[i][j]中寻找，其中j≥i+Nj \ge i + Nj≥i+N，表示覆盖了至少NNN条连续的边，即覆盖了整个多边形。

5. 算法步骤总结

1. 读取输入：多边形顶点和灯的信息
2. 生成区间：对于每盏灯，找出它能照亮的最长连续边段，并转换为合适的区间表示
3. 动态规划：使用上述动态规划方法计算最小成本
4. 判断答案：如果最小成本为无穷大，则输出Impossible.，否则输出该成本

复杂度分析

• 几何判断：O(M×N)O(M \times N)O(M×N)
• 区间生成：O(M×N)O(M \times N)O(M×N)
• 动态规划：状态数O(N2)O(N^2)O(N2)，转移O(M×N)O(M \times N)O(M×N)，总复杂度O(M×N2)O(M \times N^2)O(M×N2)
• 由于N≤30N \le 30N≤30，M≤1000M \le 1000M≤1000，计算量在可接受范围内

代码实现

// Barisal Stadium// UVa ID: 10641// Verdict: Accepted// Submission Date: 2025-12-21// UVa Run Time: 0.010s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintINF=0x3f3f3f3f,MAXN=32,MAXM=1024;structPoint{intx,y;Point(){}Point(intx,inty):x(x),y(y){}Pointoperator-(constPoint&b)const{returnPoint(x-b.x,y-b.y);}intdot(constPoint&b)const{returnx*b.x+y*b.y;}};intn,m;Point poly[MAXN],lights[MAXM];intcosts[MAXM];// 判断灯是否能照亮边ab（从顶点a到b）boolcanCover(intlightIdx,inta,intb){Point edge=poly[b]-poly[a];// 外法向量（顺时针旋转90度）Pointnormal(edge.y,-edge.x);// 从灯到顶点a的向量Point vec=lights[lightIdx]-poly[a];// 法向量与光线向量夹角为锐角 => 点积 > 0returnnormal.dot(vec)>0;}structInterval{intl,r,cost;booloperator<(constInterval&other)const{// 先按起点排序，再按终点排序if(l!=other.l)returnl<other.l;returnr<other.r;}};// 直接生成所有可能区间vector<Interval>getAllIntervals(){vector<Interval>intervals;for(inti=0;i<m;i++){// 找到第一个可以覆盖的顶点区间intleft=-1,right=-1;for(intj=0;j<n;j++){if(canCover(i,j,(j+1)%n)){left=j;right=(j+1)%n;break;}}// 因为是凸多边形，一盏灯不可能覆盖所有边，所以向左侧和右侧扩展时必定不会相遇// 向左侧扩展while(canCover(i,(left-1+n)%n,left))left=(left-1+n)%n;// 向右侧扩展while(canCover(i,right,(right+1)%n))right=(right+1)%n;// 调整覆盖区间if(left<right)intervals.push_back({left,right,costs[i]});elseintervals.push_back({left,right+n,costs[i]});}// 按照覆盖区间的左端点优先进行排序sort(intervals.begin(),intervals.end());returnintervals;}intsolve(){// 获取所有灯的覆盖区间（已排序）vector<Interval>intervals=getAllIntervals();// 状态定义：dp[i][j]从顶点i开始覆盖，覆盖到顶点j之间的边的最小费用intdp[64][64];memset(dp,0x3f,sizeofdp);for(inti=0;i<n;i++)dp[i][i]=0;for(autoitl:intervals){intlast=itl.l;for(inti=0;i<=last;i++){if(dp[i][last]==INF)continue;for(intj=itl.l+1;j<=itl.r;j++)dp[i][j]=min(dp[i][j],dp[i][last]+itl.cost);}}// 确定最小费用，注意：覆盖区间长度必须为nintanswer=INF;for(inti=0;i<n;i++)for(intj=i+n;j<2*n;j++)answer=min(answer,dp[i][j]);returnanswer;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);while(cin>>n&&n){for(inti=0;i<n;i++)cin>>poly[i].x>>poly[i].y;cin>>m;for(inti=0;i<m;i++)cin>>lights[i].x>>lights[i].y>>costs[i];intresult=solve();if(result==INF)cout<<"Impossible.";elsecout<<result;cout<<'\n';}return0;}

总结

本题的关键在于将几何问题转化为区间覆盖问题，并利用动态规划求解。主要技巧包括：

1. 几何判断简化：通过点积判断照亮条件，避免复杂的角度计算
2. 连续覆盖性质：利用凸多边形的特性，将灯覆盖范围表示为连续区间
3. 环形处理：通过复制区间和调整端点，将环形问题转化为线性问题
4. 动态规划优化：使用dp[i][j]dp[i][j]dp[i][j]状态表示覆盖区间的最小成本

这个解法充分利用了题目的限制条件（N≤30N \le 30N≤30），在时间和空间上都是高效的。通过本题，我们学习了如何将复杂的几何问题与经典的区间覆盖动态规划相结合，这是一个很好的算法设计范例。