高考又來了，對于不認真讀書的來講真不是個好消息。為了小楊能在家里認真讀書，他的親戚決定駐扎在他的家里監督他學習，有爺爺奶奶、外公外婆、大舅、大嫂、阿姨…… 小楊實在是忍無可忍了，這種生活跟監獄有什么區別！為了他親愛的小紅，為了他的dota，他決定越獄！ 假設小楊的家是個n*m 的矩陣，左下角坐標為（0，0），右上角坐標為（x1，y1）。小楊有n 個親戚，駐扎在矩陣里（位置不同，且不在矩陣的邊上）。小楊家里的每個地方都被親戚監控著，而且只被距離最近的親戚監控： 也就是說假設小楊所在的位置是（3,3），親戚A 在（3,0），A 距離小楊距離是3；親戚B 在（6,7），則B 距離小楊距離是5。距離A < 距離B，所以（3,3）位置由A 監控。 如果“最近距離”出現同時有幾個親戚，那么那個位置同時被那幾個親戚監控。 給出小楊的坐標（x0,y0）。因為被發現的人數越少，越獄成功的機會越大，所以小楊需要你設計一條越獄路線到達矩形的邊上，且被發現的人數最少。 Ps：小楊做的方向是任意的，也就是說路線上的任意位置只需要是實數。 保證一開始小楊只被一個親戚監控著。
顯然，每個點與其他點連線的中垂線形成的半平面求交，就是這個點的監視范圍。 然后最短路即可。
1.半平面交的流程 1)加入半平面以及四個特殊的邊界半平面； 2)按半平面的極角排序，極角相同的半平面取較內側的一個； 3)利用雙端隊列求出半平面交，頭尾都要檢查交點是否在新加入的半平面內； 注意：判斷無解（隊列中只剩一個半平面） 4)隊列尾交點是否在頭半平面中
新聞熱點
疑難解答
