題目：http://poj.org/problem?id=1113
順時鐘給出由n個點組成的城堡輪廓(是簡單多邊形)
現在要造一道城牆包住城堡、並且城牆上任一點和城堡任一點的距離不能小於L
問最短城牆的長度
(題目沒說要多筆輸入...)
程式碼：http://codepad.org/Z4bwxYAj
首先想到用Graham掃描法求凸包(會是最優的城牆結構，直覺略證明)
然後在紙上隨便畫個多邊形、用圓規模擬一下會發現
整個城牆是圓弧部分+公切線部分組成
公切線長就是凸包長
圓弧部分發現每一個圓角都是180-對應凸包角
所以圓弧角度的總和就恰好是360度
答案就是凸包長+半徑L的圓周長
沒有留言:
張貼留言