問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_6_A 書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」で紹介されいるが、セグ木を使って効率よく解けると書いてあったので実装。 x座標を座標圧縮すると平面走…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2201金属棒の候補となる直線は ２円の共通内・外接線 ２円の内一方の半径にmを足したものと他方の円の共通内・外接線 両方の半径にmを足したものの共通内・外接線 の３通り。これを全列挙…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0010前に通したコードを書き直したので。 #include<iostream> #include<vector> #include<algorithm> #include<cmath> #include<cstdio> using namespace std; typedef double Real; Real EPS = 1e-8; int sgn(Real a, Real b=0){return</cstdio></cmath></algorithm></vector></iostream>…

問題文 https://icpcarchive.ecs.baylor.edu/external/56/5689.pdf色のついた円が与えられる。各データセットには色が400.0の円と789.0の円がひとつずつ含まれる。この円の上を通って、400.0の円から789.0の円に行って戻ってくることができるかどうか判定せ…

問題文 http://uva.onlinejudge.org/external/109/10991.html3つの円の半径が与えられる。図のように3つの円に囲まれた部分の面積を求めよ。 3つの円の中心を頂点とする三角形の面積から、その三角形の内部の扇型の面積を引いてやればよい。三角形の面積はヘ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1266 星と望遠鏡が与えられる。すべての望遠鏡を使って見える星の数を数えよ。 aとbをそれぞれ望遠鏡の方向ベクトルと星の位置ベクトルとすると、 cosθ=a•b/|a||b| θ=acos(a•b/|a||b|) で…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0580 座標圧縮した。 #include<iostream> #include<vector> #include<algorithm> #include<map> #define all(c) (c).begin(),(c).end() #define f first #define s second using namespace std; typedef long long ll; struct</map></algorithm></vector></iostream>…

問題文 http://uva.onlinejudge.org/external/100/10088.html単純多角形が与えらる。その中の格子点の数を求めよ。 x,y座標の範囲は絶対値1000000。 ピックの定理を使った。http://en.wikipedia.org/wiki/Pick%27s_theorem ↑ピックの定理( 格子点の数 ) = ( …

問題文 http://uva.onlinejudge.org/external/116/11665.htmlいくつかの多角形(凸とは限らない)を墨で塗りつぶしたときいくつの多角形ができるか求めよ。 点-多角形包含判定。本番はライブラリが間違ってたらしく通せなかった。spaghetti sourceさんを参考に…

問題文 http://uva.onlinejudge.org/external/111/11130.html横a,縦bインチのビリヤード台があって、その中央から玉を反時計周りにA度の角度に速度vで打ち出す。この玉はs秒間動くが、摩擦でスピードが減ってしまう。ビリヤード台の縦の壁と横の壁に玉が当た…

モンテカルロ法で図形の面積を求めることができる。x*x/4+y*y=1 の式で示される楕円の面積をモンテカルロ法で求める。乱数 0≦x≦2 , 0≦y≦1 を2×1の長方形の中に均一に落とす。 1/4の楕円の中に入った乱数の数をr 落とした乱数の総数をn 1/4の楕円の面積をSと…

モンテカルロ法で円周率を求めるプログラムを簡単に書いてみた。 円周率の計算にはもっとよい方法があるのでこの方法は使われていない。1辺の長さが1の正方形とそれに内接する4分の1円(扇形)がある。正方形の面積 : 扇形の面積 = 1 : π / 4この正方形のなか…

問題文 http://uva.onlinejudge.org/external/115/11579.html辺の長さがいくつか与えられるので 作ることができる三角形の最大の面積を求めなさい。 ソートして連続する三つの辺を使った三角形が候補になる。 それを全部試して面積を求めた。 面積求めるのは…

問題文 UVa http://uva.onlinejudge.org/external/101/10117.htmlPOJ http://poj.org/problem?id=1271 高さhの牛乳に凸多角形のパンをk回浸す。 牛乳に浸されたパンの面積の最大値を求めよ。 パンの辺との距離がhかつ辺に平行な直線でパンを切り取る。 これ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0531 座標圧縮してからテープ張って幅優先探索で領域の数を数えた。 テープ張るのは↓のimosさんのやり方を参考にした。 http://imoz.jp/algorithms/imos_method.html #include<iostream> #include<vector> #i</vector></iostream>…

n個の点が与えられるので移動する時間の最大値が 最小になるような点を求める問題。 http://d.hatena.ne.jp/y_mazun/20121218/1355851934 ↑y_mazunさんの解法を参考にして解いた。 #include<iostream> #include<cmath> #include<cstdio> #include<vector> #include<algorithm> using namespace std; doubl</algorithm></vector></cstdio></cmath></iostream>…

多角形の頂点がn個反時計回りに与えられる。 多角形の各頂点と多角形の内側の点Cを端点とする線分が 全て多角形の内側にあるような点Cが存在するような 多角形をstar shapeとする。 与えられた多角形がstar shapeであるかどうか判定する問題。 十分に大きい…

n個の黒い点とm個の白い点が与えられる。 黒い点と白い点を1本の直線でわけることが できるかどうかを判定する問題。 黒い点と白い点をそれぞれを凸包してから 2つの多角形が交差するかどうか判定した。 #include<cmath> #include<algorithm> #include<iostream> #include<vector> #include<climits> #incl</climits></vector></iostream></algorithm></cmath>…

xy平面上にN個の点が与えられるので、半径1の円を動かして 囲むことができる点の個数の最大値を求める問題。 ２つの点を円周上にもつ円が最大値の候補になる。 N個の点の中から２点を決めて、その2点を円周上にもつ円を挙げ 囲まれている点の数を数えた。２…

多角形の頂点の個数と頂点座標が時計回りに与えられるので 多角形の面積を求める問題。http://www004.upp.so-net.ne.jp/s_honma/urawaza/area2.htm ↑を参考に多角形の面積を求める関数を実装した。 #include<cmath> #include<algorithm> #include<iostream> #include<vector> #include<cstdio> #define cu</cstdio></vector></iostream></algorithm></cmath>…

最近点対問題を蟻本を参考に実装。 #include<cmath> #include<algorithm> #include<iostream> #include<vector> #include<climits> #include<cfloat> using namespace std; double EPS = 1e-10; double add(double a, double b){ if(abs(a+b) < EPS * (abs(a)+abs(b)))return 0; return a+b; } struct point{ doubl</cfloat></climits></vector></iostream></algorithm></cmath>…

与えられた点の集合の中から最大の正方形を探し 面積を出力する問題。２点を決めると、正方形の残り２点が決まるので 残りの２点を二分探索で探した。 #include<iostream> #include<vector> #include<cmath> #include<algorithm> using namespace std; double EPS = 1e-10; double add(double a, </algorithm></cmath></vector></iostream>…

与えられた点と同じ形を点の集合の中から探し、 平行移動する量を出力する問題。二分探索で一つずつ探した。 #include<iostream> #include<vector> #include<set> #include<climits> #include<cfloat> #include<cmath> #include<algorithm> using namespace std; double EPS = 1e-10; double add(double a, double b){ i</algorithm></cmath></cfloat></climits></set></vector></iostream>…

点が三角形の内部にあるかを判定する。解答中の関数 dot()→内積 cross()→外積 is_point_on_line()→点が線分の上にあるか。 is_intersected_ls()→線分の交差判定。 inside()→点が多角形の内部にあるか。関数 inside(point p, vector ps) 点pが多角形psの内部…