摘要: 強(qiáng)烈推薦此題。半平面交算法的一個(gè)應(yīng)用。
具體做法是，把多邊形的每條邊向內(nèi)平移r單位長度，用這些線段所在直線和原多邊形作半平面交，得到的區(qū)域就是半徑為r的圓放入多邊形的可行域。可以證明這個(gè)區(qū)域一定是凸的，或者退化為一條線段，或一個(gè)點(diǎn)。那么，我們就可以在這個(gè)區(qū)域上求最遠(yuǎn)點(diǎn)對啦。
我的做法是O(n^2)的。應(yīng)該存在O(nlogn)的做法，因?yàn)槎际峭苟噙呅危看伟肫矫娼恢挥凶疃鄡蓚€(gè)交點(diǎn)，可二分，而最后的求最遠(yuǎn)點(diǎn)對可以旋轉(zhuǎn)卡殼。比賽的時(shí)候時(shí)間少，就寫了個(gè)暴力O(n^2)的。
閱讀全文