C++相談室 part85
■ このスレッドは過去ログ倉庫に格納されています
0388デフォルトの名無しさん
2010/10/21(木) 22:44:17総当りより少しましな方法。計算量は総当りがO(n^4)、本手法はO(n^3)
指針は、「全ての2点の組について、それら2点を対角とする最大の四角形を求める」
・2点を対角とする最大の四角形の求め方
1. 2点A,Bを結ぶ直線ABを考える
2. ABのそれぞれの側で、ABからの距離が最大となる点C,Dを求める
3. 四角形ACBDがABを対角とする四角形で最大
■ このスレッドは過去ログ倉庫に格納されています