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

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

包含の幾何

最終更新:2019年06月26日 11:16

vivid_turtle

- view
メンバー限定 登録/ログイン
多くの人の頭(もちろんこれを書いてる人の頭も)を悩ませる問題ジャンルの一つに、幾何がある。ここでは、幾何を考える際に助けになるような典型をのせる。
なお、多くの幾何のパターンはあり本にほとんど網羅されてるので、そちらをご覧になれば幸せになります。

包含の判定


幾何の難しいところとしては、数学特有の無限の可能性を持ちうるという事が挙げられる。そのままでは全探索することもままならないのである。二分探索でうまく行く場合はいいが、そうなるのは少数である。
包含の判定では、包含判定する図形の中心座標が無限に有り得て、探索はままならない。
しかし、こういう時は、ギリギリを攻めるのが幾何の常套手段。
ギリギリを攻めるにあたっては、微小変量ずらして、変動するものに注目するのがわかりやすい。こういう変動するものは、大体制約が他より厳しいものである。

AOJ1132 Circle and Points

https://onlinejudge.u-aizu.ac.jp/problems/1132

この問題での微小変量をずらすと、

1. 内部の点は変動しない。
2. 辺の上の点は変化する。

ということで、辺の上にのってる点がキーポイントだとわかる。(少しずらしても包含される点に関しては、点の中心を微調整しても問題ないけど、辺の上に乗るという条件は少しずらしてもダメで、より厳しい。)
辺の上に1点を載せることは絶対にできるが、2点を載せることは物によって可能かどうか分かれる。3点以上は、たまたま乗っかった他はありえない。つまり、3点以上が辺上にあるのは2点が辺上にある場合を全探索すればカバーができる。
以上の事実から、2点が載るような中心を全探索すれば、辺の上のその中で最大の包含数がわかる。
「包含の幾何」をウィキ内検索
LINE
シェア
Tweet
早稲田大学チームvivid_turtle 知見共有@ ウィキ
記事メニュー

メニュー

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



リンク

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




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

更新履歴

取得中です。


ここを編集
最近更新されたページ
  • 1504日前

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

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

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

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

    ARC096-D
  • 2122日前

    ARC092-D
  • 2122日前

    個別問題知見
  • 2126日前

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

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

    数え上げのDPのさまざま(知らなかったこと)
もっと見る
最近更新されたページ
  • 1504日前

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

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

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

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

    ARC096-D
  • 2122日前

    ARC092-D
  • 2122日前

    個別問題知見
  • 2126日前

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

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

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

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

  1. MadTown GTA (Beta) まとめウィキ
  2. AviUtl2のWiki
  3. R.E.P.O. 日本語解説Wiki
  4. 機動戦士ガンダム EXTREME VS.2 INFINITEBOOST wiki
  5. シュガードール情報まとめウィキ
  6. ソードランページ @ 非公式wiki
  7. ドラゴンボール Sparking! ZERO 攻略Wiki
  8. シミュグラ2Wiki(Simulation Of Grand2)GTARP
  9. 星飼いの詩@ ウィキ
  10. Dark War Survival攻略
もっと見る
人気Wikiランキング

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

  1. アニヲタWiki(仮)
  2. ストグラ まとめ @ウィキ
  3. ゲームカタログ@Wiki ~名作からクソゲーまで~
  4. 初音ミク Wiki
  5. 検索してはいけない言葉 @ ウィキ
  6. 機動戦士ガンダム バトルオペレーション2攻略Wiki 3rd Season
  7. 発車メロディーwiki
  8. Grand Theft Auto V(グランドセフトオート5)GTA5 & GTAオンライン 情報・攻略wiki
  9. オレカバトル アプリ版 @ ウィキ
  10. SDガンダム ジージェネレーションジェネシス 攻略Wiki
もっと見る
全体ページランキング

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

  1. 過去の行動&発言まとめ - 鹿乃つの氏 周辺注意喚起@ウィキ
  2. マイティーストライクフリーダムガンダム - 機動戦士ガンダム EXTREME VS.2 INFINITEBOOST wiki
  3. 魚拓まとめ - 鹿乃つの氏 周辺注意喚起@ウィキ
  4. 参加者一覧 - ストグラ まとめ @ウィキ
  5. 1103環境(遊戯王) - アニヲタWiki(仮)
  6. 前作からの変更点 - 機動戦士ガンダム EXTREME VS.2 INFINITEBOOST wiki
  7. 魔獣トゲイラ - バトルロイヤルR+α ファンフィクション(二次創作など)総合wiki
  8. コレクター・ユイ - アニヲタWiki(仮)
  9. サーヴァント/一覧/クラス別 - Fate/Grand Order @wiki 【FGO】
  10. 画像倉庫 - 鹿乃つの氏 周辺注意喚起@ウィキ
もっと見る

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

2019 AtWiki, Inc.