Hatena::Grouptopcoder

hotpepsiの練習帳

2014-05-06

SRM 614

| 22:11

Div1 Easy (250) MinimumSquare

問題

  • N個の座標がある
  • それらのうち、K個以上の座標を含むように正方形で囲む
  • ただし辺の上にあるものは含めない
  • 最小の面積を求める

方針

  • 範囲を愚直に全て調べるのは無理なので、どこかを決めうちする
  • どういう範囲であっても、左下は存在するはず
  • 左下を決めて、その位置より右かつ上のものを覚えておく
  • 条件を満たすものがK個以上になる場合、距離でソートして、K番目のものを使う
  • 左の座標と下の座標は、それぞれ別の点の可能性がある
  • XとYそれぞれのかけあわせで試せばいい
  • Passed System Test
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_614/MinimumSquare.cpp

結果

o-- 159.79pt 239th/748 rating 1354 -> 1439 (+85)

図に描いたら思いついた。

xとyを独立で試すの割とよくあるかも。


http://togetter.com/li/648607

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140506