摘要: 強烈推薦此題。半平面交算法的一個應(yīng)用。
具體做法是，把多邊形的每條邊向內(nèi)平移r單位長度，用這些線段所在直線和原多邊形作半平面交，得到的區(qū)域就是半徑為r的圓放入多邊形的可行域?？梢宰C明這個區(qū)域一定是凸的，或者退化為一條線段，或一個點。那么，我們就可以在這個區(qū)域上求最遠點對啦。
我的做法是O(n^2)的。應(yīng)該存在O(nlogn)的做法，因為都是凸多邊形，每次半平面交只有最多兩個交點，可二分，而最后的求最遠點對可以旋轉(zhuǎn)卡殼。比賽的時候時間少，就寫了個暴力O(n^2)的。
閱讀全文