HDU 4840 ROBOT——XY射线、二分查找

比眉伴天荒 2022-05-14 01:25 158阅读 0赞

题目来源[HDU 4840][]  
**Problem Description**  
In the near future, robots are going to transport snacks to the contestants at Balkan Olympiads in Informatics. Robot carries all snacks on a single square tray. ≤Unfortunately, path between the kitchen and the contestant hall is expected to be full of various obstacles and, thus, robot won\\’t be able to carry a tray of an arbitrary size. It is your task to write a program ZAD1.EXE to determine the size of the largest possible tray that can be used for catering.  
The path that the robot is supposed to traverse is contained in the corridor with parallel walls and corridor can have only 90o turns. Corridor starts in the direction of the positive x-axis. Obstacles are pillars, represented as points, and they are all between the walls of the corridor. In order for the robot to be able to traverse the path, the tray must not hit pillars or walls – it may only \\”touch\\” them with its side. Robot and his tray move only by translation in the direction of x or y-axis. Assume that the dimensions of the robot are smaller than the dimensions of the tray and that the robot is always completely under the tray.  
**Input**  
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases.  
In the first line of the each test case, is an integer m (1 ≤ m ≤ 30) that represents the number of straight wall segments. In the next m+1 lines of the input file are the x and y coordinates of all turning points (including the endpoints) of the \\”upper\\” walls, i.e. the broken line whose initial point has a greater y coordinate. Similarly, in the next m+1 lines are the x and y coordinates of all turning points (including the endpoints) of the \\”lower\\” walls. Next line of the input file contains the integer n (0 ≤ n ≤ 100) that represents the number of obstacles. In the next n lines of the input file are the x and y coordinates of the obstacles. All coordinates are integers with absolute values less than 32001.  
**Output**  
Output should contain only one integer for each test case that represents the length of the side of the largest tray that satisfies the conditions of the problem.  
**Sample Input**  
![这里写图片描述][70]  
**Sample Output**  
5

# 问题描述 #

（建议先阅读原英文描述）  
有一个走廊，走廊里有一些障碍物，机器人会托着托盘在走廊里来回走动，但是由于走廊宽度以及障碍点的限制，机器人可以托的方形托盘的边长也是有限制的。请你求出，方形托盘在限制下可以使用的最大边长。（理解“最大”，因为边长还可以更小，但是却不能更大了）  
**抽取条件**：  
1.托盘是正方形的  
2.障碍物可以没有  
3.托盘的移动过程只是平移，但不会旋转  
4.要找到：每段走廊的最小宽度、障碍点与墙之间的最小宽度、障碍点之间的最小宽度（本文代码没有考虑、读者可自行添加），这三者的最小值。  
**排除特殊情况**：（作合理的假设）  
1.障碍点必须在走廊内  
2.障碍点必须在走廊两段墙之间

# 问题分析 #

![这里写图片描述][70 1]  
如上图所示，假设走廊和障碍点如上（只有一个障碍点），那么就只需要对障碍点分别作XY的射线就行：  
对X轴方向墙作射线，会扫到4条横线，而对于**扫不到的横线，就不作考虑，因为障碍点根本不可能再扫不到的横线的走廊里面**。对于扫到的4条横线，对应的是两段走廊，但障碍点只能在一段走廊里，所以用程序去判断障碍点到底在哪段走廊里，然后取点与墙之间距离的较小值即min(5,5)=5.  
对Y轴方向墙作射线，会扫到1根竖线，这样就构不成一段走廊，所以不用考虑。  
最后，取两个方向的距离较小值的较小值。  
![这里写图片描述][70 2]  
如上图所示，障碍点对X轴方向墙作射线，发现会有两条横线扫不到，但不用考虑这两条横线，因为障碍点根本不可能在扫不到的横线对应的走廊里。  
![这里写图片描述][70 3]  
还有一种特殊情况，当障碍点在转角处时：  
此时，对X轴方向墙作射线，每一段墙都只能扫到上墙或者下墙，所以在扫线的时候，应该是，只要走廊的上墙或者下墙被扫到，就将其纳入考虑范围内。对于上图，障碍点在第一段走廊内，然后取距离较小值min(4,6)=4.  
对Y轴方向墙作射线，此时也会扫到一段走廊了。

# 代码 #

from math import *
    class Graph():
    
        def __init__(self, m,n,up,down,obs):
            self.m = m#墙的个数
            self.n = n#点的个数
            self.up = up
            self.down = down
            self.obs = obs
            if(n == 0):#无障碍点时，就计算走廊的最小宽度
                print( self.zeroObs())
            else:
                print( self.haveObs())
        def zeroObs(self):
            flagX = True#第一段墙是x方向，所以y坐标一样
            if(up[0][1] != up[1][1]):#现在不一样了，所以取反
                flagX = False
            minValue = 0
            for i in range(m):#看每段墙的开头节点就行
                if(i == 0):
                    minValue = self.process(flagX, up[i], down[i])
                else:
                    temp = self.process(flagX, up[i], down[i])
                    if(temp < minValue):
                        minValue = temp
                flagX = not flagX#x方向过了就是y方向
            return minValue
    
        def process(self,flagX,up,down):
            if(flagX == True):#这段墙是x方向
                return abs(up[1]-down[1])
            else:
                return abs(up[0]-down[0])
    
        def haveObs(self):
            #分别对x轴方向边，和y轴方向边进行排序
            self.XEdges = []
            self.YEdges = []
            flagX = True#第一段墙是x方向，所以y坐标一样
            if(up[0][1] != up[1][1]):#现在不一样了，所以取反
                flagX = False
            for i in range(self.m):
                #这两条边同时是x轴方向或y轴方向
                self.addEdges(flagX,up[i],up[i+1],down[i],down[i+1])
                flagX = not flagX
            #不能先对边进行排序，而是先扫线，后排序
    
            result = []
            #每个障碍点，分别作x和y的射线
            for i in range(n):
                XMIN = self.XRays(self.obs[i],self.XEdges)
                YMIN = self.YRays(self.obs[i],self.YEdges)
                if XMIN:
                    result.append(XMIN)
                if YMIN:
                    result.append(YMIN)
            return min(result)
    
        #对X轴方向边作射线
        def XRays(self,obstacle,XEdges):
            minValue = None
            new = []
            #收集射线能射到的线段，至少上墙或下墙包含障碍点
            for i in range(len(XEdges)//2):#数量必为偶数
                firstWall = XEdges[2*i][0][0] <= obstacle[0] <= XEdges[2*i][1][0]
                secondWall = XEdges[2*i+1][0][0] <= obstacle[0] <= XEdges[2*i+1][1][0]
                if firstWall or secondWall:
                    new.append(XEdges[2*i][0][1])#只添加每个X轴方向边的Y坐标
                    new.append(XEdges[2*i+1][0][1])
            if not new:
                return minValue                
            #排序以方便二分查找
            new = sorted(new)
            #二分查找，找到障碍点在线段对中，的那个线段对
            low = 0 ; high = len(new)//2-1 #把线段对当成个体来二分
            while(low <= high):
                middle = (low + high) // 2
                real = middle * 2#线段对第一条线段的实际索引
                if new[real] < obstacle[1] < new[real+1]:
                    minValue = min( abs(new[real]-obstacle[1]),abs(obstacle[1]-new[real+1]) )
                    break
                if new[real] < obstacle[1]:#障碍点在上面
                    high = middle - 1
                else:
                    low = middle + 1
            return minValue
    
        #对Y轴方向边作射线 
        def YRays(self,obstacle,YEdges):
            minValue = None
            new = []
            #收集射线能射到的线段，至少上墙或下墙包含障碍点
            for i in range(len(YEdges)//2):#数量必为偶数
                firstWall = YEdges[2*i][0][1] <= obstacle[1] <= YEdges[2*i][1][1]
                secondWall = YEdges[2*i+1][0][1] <= obstacle[1] <= YEdges[2*i+1][1][1]
                if firstWall or secondWall:
                    new.append(YEdges[2*i][0][0])#只添加每个Y轴方向边的X坐标
                    new.append(YEdges[2*i+1][0][0])
            if not new:
                return minValue
            #排序以方便二分查找
            new = sorted(new)
            #二分查找，找到障碍点在线段对中，的那个线段对
            low = 0 ; high = len(new)//2-1 #把线段对当成个体来二分
            while(low <= high):
                middle = (low + high) // 2
                real = middle * 2#线段对第一条线段的实际索引
                if new[real] < obstacle[0] < new[real+1]:
                    minValue = min( abs(new[real]-obstacle[0]),abs(obstacle[0]-new[real+1]) )
                    break
                if new[real] < obstacle[0]:#障碍点在上面
                    high = middle - 1
                else:
                    low = middle + 1
            return minValue        
    
        def addEdges(self,flagX,up1,up2,down1,down2):
            if(flagX == True):
                self.XEdges.append([up1,up2])#肯定都为同一个方向
                self.XEdges.append([down1,down2])
            else:
                self.YEdges.append([up1,up2])
                self.YEdges.append([down1,down2])            
    
    
    #因为不是C++或者java，所以写在最外层的就是主函数
    #提交代码时，请取消以下注释
    # m = eval(input('直线墙的数量'))#所以转角一共有m+1个
    # up = [] ; down = [] ; obs = []
    # for i in range(m+1):
        # x,y = map(int,input('输入上段的每个转角').split())
        # up.append([x,y])
    # for i in range(m+1):
        # x,y = map(int,input('输入下段的每个转角').split())
        # down.append([x,y])
    # n = eval(input('障碍的数量'))
    # for i in range(n):
        # x,y = map(int,input('输入每个障碍物').split())
        # obs.append([x,y])
    
    #提交代码时，请删除以下代码
    m = 3
    n = 2
    up = [[0,10],[20,10],[20,-25],[-10,-25]]
    down = [[0,0],[10,0],[10,-10],[-10,-10]]
    obs = [[15,-15],[6,4]]
    
    g = Graph(m,n,up,down,obs)

运行结果：4  
解释一下，注释：不能先对边进行排序，而是先扫线，后排序。  
![这里写图片描述][70 4]  
如上图所示，如果先对边进行排序，红圈圈的两条横线会穿插在第一条走廊的两条横线中，这样就会造成，程序在分析的时候，会将两条走廊拆分重组为两条新的走廊（因为程序是以每两两相邻的两条线作为一条走廊）。而在扫线后排序，就不可能出现这种情况。

[HDU 4840]: http://acm.hdu.edu.cn/showproblem.php?pid=4840
[70]: /images/20220514/0e4f534e4c7c45b886731d31805f12d7.png
[70 1]: /images/20220514/3fbf81f4a1ec4267ac4584d3fcf54f64.png
[70 2]: /images/20220514/323c468856904126a15afe27dc21eade.png
[70 3]: /images/20220514/8d0f23f5322940819dab960d95f2eafd.png
[70 4]: /images/20220514/a7445b9e1af24b92a562d0d495c881ef.png