Posted on 2010-06-23 00:15
王之昊 閱讀(519)
評論(0) 編輯 收藏 引用 所屬分類:
初中風格的平面幾何 、
二分 、
圓
題意：有四個圓大小不一，可以隨意移動他們，求包圍這四個圓的最小園？
首先應該是二分答案，變成一個判定性問題。
對于某個固定半徑 R 的目標圓，假設它的圓心 C0 在(0,0)。其他四個圓的圓心 Pi 只要滿足 | Pi - C0 | + ri <= R 即可。可以想象Pi 應當盡量的離 C0越遠越好， 越遠越有希望放下，當然在滿足上面的條件下。
這樣四個圓的圓心離原點的距離就確定了，現在可以想像成有
四個杠桿,每個杠桿的頭上有一個圓,杠桿可以繞著原點轉動,圓是剛性的,接著就判斷這種情況是否可能發生.
實際上只要讓他們一個挨著一個放就可以了.比如可以 放置第i個時,盡量挨著逆時針方向的前i-1個,并且判斷會不會沿順時針方向和前i-1個沖突.
這里還有些不太清楚的地方:比如順序是否有關?