hotpepsiの練習帳

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