Introduction

ブログ内検索

  • このサイトの記事を検索 by Google

おすすめの一冊!

無料ブログはココログ

« TopCoder の「探索」 | トップページ | 「いつふぉろ」リニューアル »

2010-02-07

TopCoder 連載第1回の問題

昨日の記事の連載「最強最強アルゴリズマー養成講座 -- ITmedia」の
バックナンバーを順に追ってみることにしました。

まずは第1回。肩慣らしですね。

  ⇒ 問題(と解答)

あっさり解けました。それでも15分かかりましたが・・・


;; TopCoder (SRM Div2Easy)
;; http://www.itmedia.co.jp/enterprise/articles/0908/01/news001_2.html

; すべての円について、以下を調べる:
;  ・始点と終点がともに円周内にある場合は円周をまたぐ必要はない。
;  ・始点と終点がともに円周外にある場合は円周をまたぐ必要はない。
;  ・片方だけが円周内にある場合は円周をまたがなければならない。


(defun solve (x1 y1 x2 y2 circles)
  (labels ((second-power (x) (* x x))
           (distance (p0 p1)
             (+ (second-power (- (car p0) (car p1)))
                (second-power (- (cadr p0) (cadr p1)))))
           (is-inside (p circle)
             (< (distance p circle) (second-power (caddr circle)))))
    (count-if #'(lambda (c) (xor (is-inside (list x1 y1) c) (is-inside (list x2 y2) c))) circles)))

;====================

(solve 0 0 10 10 '((0 0 2) (5 5 2) (10 10 2)))  ; = 2
(solve 0 0 10 10 '((0 0 20) (5 5 2) (10 10 2))) ; = 1
途中、count-if 関数を手書きしそうになりましたが、 考え直して xyzzy refwiki で検索して count-if を発見。 まぁ、無いわけ無いですよね・・・

« TopCoder の「探索」 | トップページ | 「いつふぉろ」リニューアル »