ICPC/domestic/2004D

出展 †

• ICPC国内予選2004 問題文(AOJ)

解法 †

• 点を1個含む円が存在する事は明らかなので，点を2個以上含む円を考える
  • 円を2個以上含む円は，どれか2点が円周上に乗るように移動できる
  • よって距離2未満の2点から距離1にある点を中心とする円について内包する点の数を調べれば良い
  • 点の数nについて，円の中心点の候補がO(n^2)，内包判定がO(n)で，計算量はO(n^3)

回答 †

• 2004D_pes.cpp - 上解法と関係ないヒューリスティックな解法(pes)