ICPC夏合宿09 Day2 Problem F Voronoi Island ~ボロノイ島戦記~

Slides:



Advertisements
Similar presentations
Problem A : Everlasting...? 原案 : 泉 模範解答 : 黄・野田 解説 : 野田.
Advertisements

G 問題 コードアート オンライン 原案:西出 ライタ:伊藤 テスタ:西出. 問題概要 0 大きさのさまざまな n 個の円に多角形 m 個を入れら れるか判定する問題 0 ただし、同じ円に複数の多角形を入れることはでき ない 0 もし、入れられる場合は、辞書順最小の入れ方を出 力 ① ② ③ ① ②.
原案 : 野田 解答 : 野田・山 口 問題文 : 野田 PROBLEM E: PSYCHIC ACCELERATOR ~ とある超能力の物体加速器~
模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
J: Magical Switches JAG 模擬地区予選 2013 原案:保坂 解答:保坂・楠本 解説:保坂.
Problem J: いにしえの数式 問題作成・解説: 北村 解答作成協力: 八森.
ICPC夏合宿09 Day3 Problem D : Luigi‘s Tavern -ルイージの酒場-
Revenge of the Round Table
Day2 Problem I: Memory Match ~神経衰弱~
Problem H: Queen’s case
豊中高校土曜講座「数学セミナー2003」 プラトン多面体の数学 なぜ正多面体は5種類しかないのか 大阪府立豊中高等学校 深川 久.
原案:西出 テスト 伊藤.
塩山幾何学を用いたボロノイ図の解析 立命館高校 三村 知洋 宮崎 航輔 村田 航大 ■ 研究概要 ■ ■ 研究動機 ■ 1 塩山幾何学とは
中学数学1年 5章 平面図形 §1 図形の基礎と移動 (7時間).
I: Tokyo Olympics Center
Intelligent Circular Perfect Cleaner(ICPC)
Princess, a Strategiest
問題作成・解説: 北村 解答作成協力: 小西・松本
2点A(2,4)、B(-3,1)の距離を求めてみよう。
有効数字 有効数字の利用を考える.
Problem G : Entangled Tree
3 一次関数 1章 一次関数とグラフ §3 一次関数の式を求めること          (3時間).
Problem H ねこ鍋改造計画(仮) 秋葉 拓哉.
原案:阿部 担当:福澤, 笠原 英訳:寺島 解説:福澤
C言語 配列 2016年 吉田研究室.
JAG Regional Practice Contest 2012 問題C: Median Tree
原案: 矢藤(kohyatoh) 解答: 高原(rankalee, shimejitan), 矢藤 解説: 矢藤
シミュレーション論Ⅰ 第4回 基礎的なシミュレーション手法.
形状モデリングにおいて,任意の自由曲面を定義する必要のある場合がある.自由曲面の表現法について説明する.
Problem C: Princess' Japanese
模擬国内予選2014 Problem C 壊れた暗号生成器
2013年度模擬アジア地区予選 Problem E: Putter
Problem D: King Slime ~キングスライム~
    有限幾何学        第13回.
実習4 2次元テーブルの利用 フローチャートの作成.
4章 平行と合同 2 多角形の外角の和.
Problem F Two-finger Programming
原案・解説 : 野田 解答 : 野田・吉田 Problem D Futon ~布団~.
塩山幾何学を用いた ボロノイ図の解析 立命館高等学校 三村 知洋 宮崎 航輔 村田 航大 塩山幾何学を用いたボロノイ図の解析
講義日程 第1回: 投影法とその種類 第2回: 点及び直線の投影 第3回: 副投影法 第4回: 平面の投影
形式言語とオートマトン Formal Languages and Automata 第4日目
形式言語とオートマトン Formal Languages and Automata 第4日目
三角形や四角形ではない図形の 角の大きさの和を求めよう。.
本時のねらい 「直角三角形の合同条件を導き、それを理解し、証明ができるようにする。」
形式言語とオートマトン Formal Languages and Automata 第4日目
本時のねらい 「三角形の1辺に平行な直線が他の2辺と交わるとき、それぞれの交点は、その2辺を等しい比に分けることを理解する。」
演習1 : インターフェイスを使ってみよう 「10人の客(乗用車、バイク、ストーブのいずれかランダムに決定)に1~100(L)の給油をするガソリンスタンドをシミュレートする実行クラス : RefuelSimulation」を作成する。給油の際には、どの種類の客が何リットル給油したか出力すること。 実行結果例.
平行線と面積 平行な直線と面積の 関係を考えます。.
本時のねらい 「二等辺三角形の作図から証明を使って性質を導くことができる。」 「定義や定理の用語の意味を理解する。」
本時のねらい 「図形の中から相似な三角形を見出し、相似条件を用いて証明することができる。」
古代の難問と曲線 (3時間目) 筑波大学大学院 教育研究科 1年                 石井寿一.
都市・港湾経済学(総) 国民経済計算論(商)
5 図形と合同 1章 三角形 §1 二等辺三角形         (4時間).
中学数学1年 5章 平面図形 §2 作図 (3時間).
宝 探 し 本時の目標 これまで学習してきた作図を利用して、条件を満たす点の作図をすることができる。
平行線の性質を使って、面積の等しい図形について考えてみよう。
多角形の外角の和 凹型四角形の角 星形五角形の内角の和
V. 空間操作.
第3回 基礎作図 基本的な作図法をしっかりと学ぶ! 本日の課題.
D: 壊れかけのヒープ 問題案: 稲葉.
かけ算九九は 言えるようになったかな? じゃ、 かけ算ビンゴを やってみよう。.
5年 算数 「面積(平行四辺形)」.
博士たちの愛する円周率 徳山 豪 東北大学 “PI” that professors love
利用者の制限領域を 最小化する施設配置問題 :中学校配置の評価
指令1 三角形の謎にせまれ!.
下の図のように、直角三角形と正方 形が直線ℓ上に並んでいる。 8cm 8cm ℓ 8cm 8cm.
形式言語とオートマトン Formal Languages and Automata 第5日目
C問題 高所恐怖症 原案・ライタ : 伊藤 テスタ : 青木・西出.
3 一次関数 1章 一次関数とグラフ §4 方程式とグラフ         (3時間).
コンピュータの高速化により, 即座に計算できるようになってきたが, 手法的にはコンピュータ出現以前に考え出された 方法が数多く使われている。
Presentation transcript:

ICPC夏合宿09 Day2 Problem F Voronoi Island ~ボロノイ島戦記~ 原案 : 桜庭 解答 : 牟田・高橋 解説 : 野田

問題 凸多角形の内部に点が与えられる。 ボロノイ分割した際の各領域の面積を求めよ

解答例 各頂点について「凸多角形の切断」を用いて 垂直二等分線で凸多角形を切断し、面積を求 める

凸多角形の切断 Spaghetti Source - 凸多角形の切断 http://www.prefield.com/algorithm/geometry/c onvex_cut.html 凸多角形をある直線で切断し,その左側だけ残す. 直線よりも左側にあるものと,交差するときはそ の交点を出力として吐いている. 何度も切断を繰り返す場合,誤差が積み重なるた め,切りそこねが発生することがある.端点を切 り落とさないようにあらかじめ多角形を摂動する と対処できるかもしれない. 以上、コピペ 詳しくはホームページを参照のこと

ジャッジソースコード 牟田 C++ 629行 高橋 94行

結果 First submit : Watch.d (95) First accepted : Watch.d (110) Total submit : 7 Total accepted : 5

一言 Revenge of Voronoiもよろしく!