いがメモスマートフォン用の表示で見るいがメモプログラミング関連についてやったことの記録を書いていきます。この広告は、90日以上更新していないブログに表示しています。StatementN(1<=N<=100)個の点のX座標とY座標が与えられる。1,000,000,000)K個(1<=K<=N)の点を含み、軸に平行で四隅の点の座標が整数である正四角形の最小の面積を求めよ。解いた方法:最初、ある1点を四隅に決め打ちして残りのもう1点を探索し、内包する点の数を数えればいいかと思ったらコーナーケースを見つけて断念。(十字に4点が置かれているケース)K=1,K=2,K=3,それ以外の4つのケースで場合分けして計算。・K=1のとき適当などっかの点が含まれていればいいので4を返す。・K=2のとき2つの点を全探索して最小の面積を探す。・K=3のとき3つの点を全探索して最小の面積を探す。・K<=4のとき4点決め打ちしてその中にある点の数を数える。すれば十字のケースの際をカバーできる。O(NC4*N)で約4000万となり、頑張れば通る。17日目]カテゴリーはてなブログをはじめよう!iga_cさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。