题目分析本题描述了一个有趣的几何与路径规划问题在一个宽度为WWW、长度为LLL的矩形过道中存在NNN个障碍物视为点。一个人从过道左侧移动到右侧在俯视图中这个人是一个不可压缩的圆盘直径为ddd。当两个障碍物之间的距离小于ddd时人无法从它们之间穿过注意题目中给出的判定条件是直径为ddd的人无法通过距离小于ddd的两个障碍物之间的缝隙。这意味着人的圆心可以无限接近障碍物只要圆盘边缘不碰到障碍物即可。类似地人也不能穿过墙壁因此圆心距离上墙壁和下墙壁至少为d/2d/2d/2。但题目简化了建模方式将人的直径ddd直接与障碍物之间的距离比较并将墙壁视为特殊的“障碍物”。具体建模方法如下上墙壁可以看作一个“虚拟障碍物”当人的直径ddd大于障碍物到上墙壁的距离时该障碍物与上墙壁“连通”。下墙壁类似。如果两个障碍物之间的欧几里得距离小于ddd则它们“连通”。最终如果上墙壁和下墙壁通过这些“连通关系”连接到了同一个连通分量中那么人就无法从左侧穿到右侧因为上下被堵住了。反之如果上下墙壁不连通则存在一条从左到右的通道。解题思路1. 问题转化假设人的直径为ddd。我们定义障碍物iii与上墙壁的距离为W−YiW - Y_iW−Yi若W−YidW - Y_i dW−Yid则障碍物iii与上墙壁连通。障碍物iii与下墙壁的距离为YiY_iYi若YidY_i dYid则障碍物iii与下墙壁连通。两个障碍物iii、jjj之间的欧氏距离dist(i,j)(Xi−Xj)2(Yi−Yj)2dist(i,j) \sqrt{(X_i - X_j)^2 (Y_i - Y_j)^2}dist(i,j)(Xi−Xj)2(Yi−Yj)2若dist(i,j)ddist(i,j) ddist(i,j)d则它们连通。我们构造一个图节点包括所有障碍物以及两个特殊节点top代表上墙壁和bottom代表下墙壁。如果两个节点满足上述连通条件则在它们之间连一条无向边。那么人能否从左到右通过答案是如果存在一条从top到bottom的路径则上下墙壁连通意味着人的直径太大被障碍物堵住了无法通过反之如果没有这样的路径则人可以通过。2. 单调性显然直径ddd越大越容易连通因为条件更宽松所以top与bottom是否连通关于ddd是单调的当ddd很小时没有连通人可以轻松通过。随着ddd增大连通性逐渐出现一旦top和bottom连通更大的ddd也会保持连通。因此我们可以使用二分查找来找到最大可行的ddd即临界点小于该值时上下不连通大于该值时上下连通。3. 二分查找边界下界low 0.0人可以无限瘦。上界high W因为直径最大不可能超过过道宽度否则圆盘无法放入过道。实际上更精确的上界可以是WWW本身或者最大的障碍物间距等但WWW是安全且方便的选择。二分查找终止条件当high - low足够小如10−910^{-9}10−9时停止输出low作为答案。4. 判断函数squeezeThrough(d)该函数判断当直径为ddd时人是否能通过调用build(d)构建图。从top开始执行DFS\texttt{DFS}DFS或BFS\texttt{BFS}BFS。如果bottom被访问到说明上下连通返回false无法通过否则返回true可以通过。5. 图的构建设障碍物索引为0∼N−10 \sim N-10∼N−1top Nbottom N1。两两障碍物间若距离 d连边。障碍物与top若W−YidW - Y_i dW−Yid则连边top-i。障碍物与bottom若YidY_i dYid则连边i-bottom。注意代码中没有为top和bottom之间的直接连边因为它们之间没有物理意义。算法复杂度每个测试用例二分查找约log2(W10−9)≈60\log_2(\frac{W}{10^{-9}}) \approx 60log2(10−9W)≈60次迭代。每次squeezeThrough需要构建图O(N2)O(N^2)O(N2)计算距离并建边。每次DFS\texttt{DFS}DFSO(NE)O(N E)O(NE)其中E≤N22NE \le N^2 2NE≤N22N。N≤100N \le 100N≤100因此总复杂度很低。边界情况当W0W 0W0时过道宽度为000只能通过直径为000的人直接输出0.0000。当N0N 0N0时没有障碍物最大直径为WWW二分查找会正确收敛到WWW。代码实现带注释// Fatman// UVa ID: 295// Verdict: Accepted// Submission Date: 2016-06-03// UVa Run Time: 0.870s//// 版权所有C2016邱秋。metaphysis # yeah dot net// http://www.algorithmist.com/index.php/UVa_295#includebits/stdc.husingnamespacestd;vectorpairint,intobstacles;// 存储所有障碍物的坐标 (X, Y)vectorvectorintedges;// 邻接表表示的图vectorboolvisited;// DFS 访问标记intL,W,N,top,bottom;// L: 过道长度(本题中未使用), W: 宽度, N: 障碍物数量// top: 上墙壁节点索引, bottom: 下墙壁节点索引// 计算两个障碍物之间的欧几里得距离doubledistances(pairint,intx,pairint,inty){returnsqrt(pow(x.first-y.first,2)pow(x.second-y.second,2));}// 根据给定的直径 d 构建图voidbuild(doublediameter){edges.clear();// 图中共有 N 个障碍物 2 个虚拟墙壁节点for(inti0;iobstacles.size()2;i)edges.push_back(vectorint());// 构建障碍物之间的边距离小于 diameter 则连通for(inti0;iobstacles.size();i){for(intji1;jobstacles.size();j)if(distances(obstacles[i],obstacles[j])diameter){edges[i].push_back(j);edges[j].push_back(i);}// 障碍物 i 与上墙壁的边障碍物到上边界的距离 diameterif(W-obstacles[i].seconddiameter)edges[top].push_back(i);// 障碍物 i 与下墙壁的边障碍物到下边界的距离 diameterif(obstacles[i].seconddiameter)edges[i].push_back(bottom);}}// 深度优先遍历voiddfs(intvertex){visited[vertex]true;for(inti0;iedges[vertex].size();i)if(visited[edges[vertex][i]]false)dfs(edges[vertex][i]);}// 判断直径为 diameter 时人能否通过// 返回 true 表示能通过上下墙壁不连通// 返回 false 表示不能通过上下墙壁连通boolsqueezeThrough(doublediameter){build(diameter);// 根据直径构建图fill(visited.begin(),visited.end(),false);// 重置访问标记dfs(top);// 从上墙壁开始 DFSreturnvisited[bottom]false;// 如果下墙壁未被访问则上下不连通可以通过}intmain(intargc,char*argv[]){intcases;cincases;for(intruns1;runscases;runs){cinLWN;obstacles.clear();for(inti1,x,y;iN;i){cinxy;obstacles.push_back(make_pair(x,y));}// 特殊情况宽度为 0只能通过直径为 0 的人if(W0){coutMaximum size in test case runs is ;coutfixedsetprecision(4)(double)W.endl;continue;}// 设定虚拟墙壁节点的索引topobstacles.size();// 上墙壁编号为 Nbottomobstacles.size()1;// 下墙壁编号为 N1visited.resize(obstacles.size()2);// 二分查找最大可行的直径doublehighW,low0.0,middle;while(fabs(high-low)1E-9)// 精度 1e-9{middle(highlow)/2.0;if(squeezeThrough(middle))// 若可以通过尝试更大的直径lowmiddle;else// 若不能通过减小直径highmiddle;}coutMaximum size in test case runs is ;coutfixedsetprecision(4)low.endl;}return0;}总结本题的核心在于将几何可行性问题转化为图论中的连通性问题人的直径ddd决定了“连通”的阈值。通过将上下墙壁视为特殊节点可以判断ddd是否导致上下墙壁连通。利用单调性进行二分查找高效求得最大可行直径。
UVa 295 Fatman
题目分析本题描述了一个有趣的几何与路径规划问题在一个宽度为WWW、长度为LLL的矩形过道中存在NNN个障碍物视为点。一个人从过道左侧移动到右侧在俯视图中这个人是一个不可压缩的圆盘直径为ddd。当两个障碍物之间的距离小于ddd时人无法从它们之间穿过注意题目中给出的判定条件是直径为ddd的人无法通过距离小于ddd的两个障碍物之间的缝隙。这意味着人的圆心可以无限接近障碍物只要圆盘边缘不碰到障碍物即可。类似地人也不能穿过墙壁因此圆心距离上墙壁和下墙壁至少为d/2d/2d/2。但题目简化了建模方式将人的直径ddd直接与障碍物之间的距离比较并将墙壁视为特殊的“障碍物”。具体建模方法如下上墙壁可以看作一个“虚拟障碍物”当人的直径ddd大于障碍物到上墙壁的距离时该障碍物与上墙壁“连通”。下墙壁类似。如果两个障碍物之间的欧几里得距离小于ddd则它们“连通”。最终如果上墙壁和下墙壁通过这些“连通关系”连接到了同一个连通分量中那么人就无法从左侧穿到右侧因为上下被堵住了。反之如果上下墙壁不连通则存在一条从左到右的通道。解题思路1. 问题转化假设人的直径为ddd。我们定义障碍物iii与上墙壁的距离为W−YiW - Y_iW−Yi若W−YidW - Y_i dW−Yid则障碍物iii与上墙壁连通。障碍物iii与下墙壁的距离为YiY_iYi若YidY_i dYid则障碍物iii与下墙壁连通。两个障碍物iii、jjj之间的欧氏距离dist(i,j)(Xi−Xj)2(Yi−Yj)2dist(i,j) \sqrt{(X_i - X_j)^2 (Y_i - Y_j)^2}dist(i,j)(Xi−Xj)2(Yi−Yj)2若dist(i,j)ddist(i,j) ddist(i,j)d则它们连通。我们构造一个图节点包括所有障碍物以及两个特殊节点top代表上墙壁和bottom代表下墙壁。如果两个节点满足上述连通条件则在它们之间连一条无向边。那么人能否从左到右通过答案是如果存在一条从top到bottom的路径则上下墙壁连通意味着人的直径太大被障碍物堵住了无法通过反之如果没有这样的路径则人可以通过。2. 单调性显然直径ddd越大越容易连通因为条件更宽松所以top与bottom是否连通关于ddd是单调的当ddd很小时没有连通人可以轻松通过。随着ddd增大连通性逐渐出现一旦top和bottom连通更大的ddd也会保持连通。因此我们可以使用二分查找来找到最大可行的ddd即临界点小于该值时上下不连通大于该值时上下连通。3. 二分查找边界下界low 0.0人可以无限瘦。上界high W因为直径最大不可能超过过道宽度否则圆盘无法放入过道。实际上更精确的上界可以是WWW本身或者最大的障碍物间距等但WWW是安全且方便的选择。二分查找终止条件当high - low足够小如10−910^{-9}10−9时停止输出low作为答案。4. 判断函数squeezeThrough(d)该函数判断当直径为ddd时人是否能通过调用build(d)构建图。从top开始执行DFS\texttt{DFS}DFS或BFS\texttt{BFS}BFS。如果bottom被访问到说明上下连通返回false无法通过否则返回true可以通过。5. 图的构建设障碍物索引为0∼N−10 \sim N-10∼N−1top Nbottom N1。两两障碍物间若距离 d连边。障碍物与top若W−YidW - Y_i dW−Yid则连边top-i。障碍物与bottom若YidY_i dYid则连边i-bottom。注意代码中没有为top和bottom之间的直接连边因为它们之间没有物理意义。算法复杂度每个测试用例二分查找约log2(W10−9)≈60\log_2(\frac{W}{10^{-9}}) \approx 60log2(10−9W)≈60次迭代。每次squeezeThrough需要构建图O(N2)O(N^2)O(N2)计算距离并建边。每次DFS\texttt{DFS}DFSO(NE)O(N E)O(NE)其中E≤N22NE \le N^2 2NE≤N22N。N≤100N \le 100N≤100因此总复杂度很低。边界情况当W0W 0W0时过道宽度为000只能通过直径为000的人直接输出0.0000。当N0N 0N0时没有障碍物最大直径为WWW二分查找会正确收敛到WWW。代码实现带注释// Fatman// UVa ID: 295// Verdict: Accepted// Submission Date: 2016-06-03// UVa Run Time: 0.870s//// 版权所有C2016邱秋。metaphysis # yeah dot net// http://www.algorithmist.com/index.php/UVa_295#includebits/stdc.husingnamespacestd;vectorpairint,intobstacles;// 存储所有障碍物的坐标 (X, Y)vectorvectorintedges;// 邻接表表示的图vectorboolvisited;// DFS 访问标记intL,W,N,top,bottom;// L: 过道长度(本题中未使用), W: 宽度, N: 障碍物数量// top: 上墙壁节点索引, bottom: 下墙壁节点索引// 计算两个障碍物之间的欧几里得距离doubledistances(pairint,intx,pairint,inty){returnsqrt(pow(x.first-y.first,2)pow(x.second-y.second,2));}// 根据给定的直径 d 构建图voidbuild(doublediameter){edges.clear();// 图中共有 N 个障碍物 2 个虚拟墙壁节点for(inti0;iobstacles.size()2;i)edges.push_back(vectorint());// 构建障碍物之间的边距离小于 diameter 则连通for(inti0;iobstacles.size();i){for(intji1;jobstacles.size();j)if(distances(obstacles[i],obstacles[j])diameter){edges[i].push_back(j);edges[j].push_back(i);}// 障碍物 i 与上墙壁的边障碍物到上边界的距离 diameterif(W-obstacles[i].seconddiameter)edges[top].push_back(i);// 障碍物 i 与下墙壁的边障碍物到下边界的距离 diameterif(obstacles[i].seconddiameter)edges[i].push_back(bottom);}}// 深度优先遍历voiddfs(intvertex){visited[vertex]true;for(inti0;iedges[vertex].size();i)if(visited[edges[vertex][i]]false)dfs(edges[vertex][i]);}// 判断直径为 diameter 时人能否通过// 返回 true 表示能通过上下墙壁不连通// 返回 false 表示不能通过上下墙壁连通boolsqueezeThrough(doublediameter){build(diameter);// 根据直径构建图fill(visited.begin(),visited.end(),false);// 重置访问标记dfs(top);// 从上墙壁开始 DFSreturnvisited[bottom]false;// 如果下墙壁未被访问则上下不连通可以通过}intmain(intargc,char*argv[]){intcases;cincases;for(intruns1;runscases;runs){cinLWN;obstacles.clear();for(inti1,x,y;iN;i){cinxy;obstacles.push_back(make_pair(x,y));}// 特殊情况宽度为 0只能通过直径为 0 的人if(W0){coutMaximum size in test case runs is ;coutfixedsetprecision(4)(double)W.endl;continue;}// 设定虚拟墙壁节点的索引topobstacles.size();// 上墙壁编号为 Nbottomobstacles.size()1;// 下墙壁编号为 N1visited.resize(obstacles.size()2);// 二分查找最大可行的直径doublehighW,low0.0,middle;while(fabs(high-low)1E-9)// 精度 1e-9{middle(highlow)/2.0;if(squeezeThrough(middle))// 若可以通过尝试更大的直径lowmiddle;else// 若不能通过减小直径highmiddle;}coutMaximum size in test case runs is ;coutfixedsetprecision(4)low.endl;}return0;}总结本题的核心在于将几何可行性问题转化为图论中的连通性问题人的直径ddd决定了“连通”的阈值。通过将上下墙壁视为特殊节点可以判断ddd是否导致上下墙壁连通。利用单调性进行二分查找高效求得最大可行直径。
