atwiki-logo
  • 新規作成
    • 新規ページ作成
    • 新規ページ作成(その他)
      • このページをコピーして新規ページ作成
      • このウィキ内の別ページをコピーして新規ページ作成
      • このページの子ページを作成
    • 新規ウィキ作成
  • 編集
    • ページ編集
    • ページ編集(簡易版)
    • ページ名変更
    • メニュー非表示でページ編集
    • ページの閲覧/編集権限変更
    • ページの編集モード変更
    • このページにファイルをアップロード
    • メニューを編集
    • 右メニューを編集
  • バージョン管理
    • 最新版変更点(差分)
    • 編集履歴(バックアップ)
    • アップロードファイル履歴
    • ページ操作履歴
  • ページ一覧
    • ページ一覧
    • このウィキのタグ一覧
    • このウィキのタグ(更新順)
    • このページの全コメント一覧
    • このウィキの全コメント一覧
    • おまかせページ移動
  • RSS
    • このウィキの更新情報RSS
    • このウィキ新着ページRSS
  • ヘルプ
    • ご利用ガイド
    • Wiki初心者向けガイド(基本操作)
    • このウィキの管理者に連絡
    • 運営会社に連絡(不具合、障害など)
ページ検索 メニュー
早稲田大学チームvivid_turtle 知見共有@ ウィキ
  • ウィキ募集バナー
  • 目安箱バナー
  • 操作ガイド
  • 新規作成
  • 編集する
  • 全ページ一覧
  • 登録/ログイン
ページ一覧
早稲田大学チームvivid_turtle 知見共有@ ウィキ
  • ウィキ募集バナー
  • 目安箱バナー
  • 操作ガイド
  • 新規作成
  • 編集する
  • 全ページ一覧
  • 登録/ログイン
ページ一覧
早稲田大学チームvivid_turtle 知見共有@ ウィキ
ページ検索 メニュー
  • 新規作成
  • 編集する
  • 登録/ログイン
  • 管理メニュー
管理メニュー
  • 新規作成
    • 新規ページ作成
    • 新規ページ作成(その他)
      • このページをコピーして新規ページ作成
      • このウィキ内の別ページをコピーして新規ページ作成
      • このページの子ページを作成
    • 新規ウィキ作成
  • 編集
    • ページ編集
    • ページ編集(簡易版)
    • ページ名変更
    • メニュー非表示でページ編集
    • ページの閲覧/編集権限変更
    • ページの編集モード変更
    • このページにファイルをアップロード
    • メニューを編集
    • 右メニューを編集
  • バージョン管理
    • 最新版変更点(差分)
    • 編集履歴(バックアップ)
    • アップロードファイル履歴
    • ページ操作履歴
  • ページ一覧
    • このウィキの全ページ一覧
    • このウィキのタグ一覧
    • このウィキのタグ一覧(更新順)
    • このページの全コメント一覧
    • このウィキの全コメント一覧
    • おまかせページ移動
  • RSS
    • このwikiの更新情報RSS
    • このwikiの新着ページRSS
  • ヘルプ
    • ご利用ガイド
    • Wiki初心者向けガイド(基本操作)
    • このウィキの管理者に連絡
    • 運営会社に連絡する(不具合、障害など)
  • atwiki
  • 早稲田大学チームvivid_turtle 知見共有@ ウィキ
  • 座標での最近点

早稲田大学チームvivid_turtle 知見共有@ ウィキ

座標での最近点

最終更新:2019年08月24日 18:26

vivid_turtle

- view
だれでも歓迎! 編集
座標での最近点を高速で求める方法を書く。
点の数はN個とする。

マンハッタン距離


とりあえず2次元だとする。多次元にも拡張できると思う。
ナイーブな実装では全点間のペアを試さないといけない。これでは、点ごとに候補がN-1個存在することになる。計算量はO(N^2)

ここで、うまく候補を絞ってみる。
今見てる頂点を(a, b)とする。
{マンハッタン距離が一番近いものは、必ず、
x座標に関しては、点の列の中でのソートされたものの中でx = aの一つ手前と一つ奥である。
同様にy座標に関しては、y = bの一つ手前と奥である。}(ソートされた列内での一つ手前や奥。ソートするとき、x軸でするものなら、第一比較にx第二比較にy、y軸でするものなら、第一比較にy第二比較にxである)
証明すると、そのうちの4つの点に入らないということは、4点に対するマンハッタン距離が同じとなる斜め45度の4つの正方形の内部に今考えてる頂点がないということである。内部にあるのならば、必ずx = aもしくはy = bにより近くなるためである。よって、その4点の候補内にマンハッタン距離最近点がある。


ARC076 D(500)


https://atcoder.jp/contests/arc076/tasks/arc076_b

この問題は上記の考え方のとおりではないが、似ている。
ある3点を考えるとき、それらをつなげるときに一番コストがかからないのは、軸ごとに独立で考えると、一つ手前か後が候補として残る。それらの候補の中で、コストの低い順にクラスカルすれば解ける。

タグ:

+ タグ編集
  • タグ:
タグの更新に失敗しました
エラーが発生しました。ページを更新してください。
ページを更新
「座標での最近点」をウィキ内検索
LINE
シェア
Tweet
早稲田大学チームvivid_turtle 知見共有@ ウィキ
記事メニュー

メニュー

  • トップページ
  • プラグイン紹介
  • メニュー
  • 右メニュー
  • アルゴリズム別知見
  • 個別問題知見



リンク

  • @wiki
  • @wikiご利用ガイド




ここを編集
記事メニュー2

更新履歴

取得中です。


ここを編集
人気記事ランキング
  1. 個別問題知見
  2. グリッド上での数え上げ
  3. AGC014-B
  4. 後ろから見ると上手くいくパターン
  5. クエリ処理でのデータ構造特有の手法
  6. 文字列と動的計画法
もっと見る
最近更新されたページ
  • 1593日前

    bitsetでの定数倍改善
  • 2207日前

    しゃくとりの大原則
  • 2207日前

    アルゴリズム別知見
  • 2210日前

    グリッド上の構築
  • 2211日前

    ARC096-D
  • 2211日前

    ARC092-D
  • 2211日前

    個別問題知見
  • 2215日前

    ダブリングの使い所さん
  • 2221日前

    文字列と動的計画法
  • 2221日前

    数え上げのDPのさまざま(知らなかったこと)
もっと見る
人気記事ランキング
  1. 個別問題知見
  2. グリッド上での数え上げ
  3. AGC014-B
  4. 後ろから見ると上手くいくパターン
  5. クエリ処理でのデータ構造特有の手法
  6. 文字列と動的計画法
もっと見る
最近更新されたページ
  • 1593日前

    bitsetでの定数倍改善
  • 2207日前

    しゃくとりの大原則
  • 2207日前

    アルゴリズム別知見
  • 2210日前

    グリッド上の構築
  • 2211日前

    ARC096-D
  • 2211日前

    ARC092-D
  • 2211日前

    個別問題知見
  • 2215日前

    ダブリングの使い所さん
  • 2221日前

    文字列と動的計画法
  • 2221日前

    数え上げのDPのさまざま(知らなかったこと)
もっと見る
ウィキ募集バナー
急上昇Wikiランキング

急上昇中のWikiランキングです。今注目を集めている話題をチェックしてみよう!

  1. デジタルモンスター まとめ@ ウィキ
  2. 神様コレクション@wiki
  3. ストグラFV まとめ@非公式wiki
  4. MADTOWNGTAまとめwiki
  5. Last Z: Survival Shooter @ ウィキ
  6. ディズニー データベース
  7. 戦国無双4シリーズ  総合攻略 @ Wiki
  8. テイルズオブ用語辞典
  9. SQ用語辞典
  10. GUNDAM WAR Wiki
もっと見る
人気Wikiランキング

atwikiでよく見られているWikiのランキングです。新しい情報を発見してみよう!

  1. アニヲタWiki(仮)
  2. ゲームカタログ@Wiki ~名作からクソゲーまで~
  3. MADTOWNGTAまとめwiki
  4. 初音ミク Wiki
  5. ストグラ まとめ @ウィキ
  6. 検索してはいけない言葉 @ ウィキ
  7. 機動戦士ガンダム バトルオペレーション2攻略Wiki 3rd Season
  8. 発車メロディーwiki
  9. MadTown GTA (Beta) まとめウィキ
  10. 機動戦士ガンダム EXTREME VS.2 INFINITEBOOST wiki
もっと見る
新規Wikiランキング

最近作成されたWikiのアクセスランキングです。見るだけでなく加筆してみよう!

  1. MadTown GTA (Beta) まとめウィキ
  2. MADTOWNGTAまとめwiki
  3. まどドラ攻略wiki
  4. ちいぽけ攻略
  5. シュガードール情報まとめウィキ
  6. 戦国ダイナスティ攻略Wiki@ウィキ
  7. Last Z: Survival Shooter @ ウィキ
  8. Shoboid RPまとめwiki
  9. ソニックレーシング クロスワールド 攻略@ ウィキ
  10. SurrounDead 攻略 (非公式wiki)
もっと見る
全体ページランキング

最近アクセスの多かったページランキングです。話題のページを見に行こう!

  1. 参加者一覧 - MADTOWNGTAまとめwiki
  2. angler - MADTOWNGTAまとめwiki
  3. 参加者一覧 - MadTown GTA (Beta) まとめウィキ
  4. 白狐 - MADTOWNGTAまとめwiki
  5. XVI - MADTOWNGTAまとめwiki
  6. 鬼レンチャン(レベル順) - 鬼レンチャンWiki
  7. Black Rose - MADTOWNGTAまとめwiki
  8. ギャング - MADTOWNGTAまとめwiki
  9. 魔獣トゲイラ - バトルロイヤルR+α ファンフィクション(二次創作など)総合wiki
  10. 参加者一覧 - ストグラ まとめ @ウィキ
もっと見る

  • このWikiのTOPへ
  • 全ページ一覧
  • アットウィキTOP
  • 利用規約
  • プライバシーポリシー

2019 AtWiki, Inc.