kmjp https://blog.hatena.ne.jp/kmjp/ kmjp's blog https://kmjp.hatenablog.jp/ SRM さて不参加だったSRM562の復習。 http://community.topcoder.com/stat?c=problem_statement&pm=11565 最初にcheckerの定義があるが、簡潔に書けば「白点と黒点の集合が与えられて、白点同士を結ぶ線と、黒点同士を結ぶ線が交差するかどうか」を求める。白点２つと黒点２つがあったとき、線が交差するかどうかは外積を使って「黒点２つが白点を結ぶ線の両側にあり、かつ白点２つが黒点を結ぶ線の両側にある」をチェックすればよい。 ただ、この方式では点を４つ選ぶのでO(N^4)かかり、N=222だと時間切れする。 よって時間の短い手法を考えなければな… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkmjp.hatenablog.jp%2Fentry%2F2012%2F12%2F24%2F0900" title="TopCoder SRM 562 Div1 Medium CheckerFreeness - kmjp&#39;s blog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2012-12-24 09:00:00 rich https://kmjp.hatenablog.jp/entry/2012/12/24/0900 1.0 100%