けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

三角形

AtCoder ARC 167 E - One Square in a Triangle (銅色, 800 点)

天才構築ゲー。これ完全自力で一発 AC できて嬉しかった!! 問題へのリンク 問題概要 正の整数 が与えられる。次の条件を満たす三角形が存在するかどうかを判定し、存在すれ場合は 1 つ求めよ。 頂点がすべて格子点であり、座標値は 以上 以下である すべて…

AtCoder ABC 116 A - Right Triangle (灰色, 100 点)

直角三角形の面積を求める問題。 問題へのリンク 問題概要 ∠ ABC = 90° の直角三角形がある。 辺 AB, BC, CA の長さが与えられるので、直角三角形の面積を求めよ。 解法 直角を挟む二辺は、AB, BC であるから、面積は と計算できる。 実装するときには、整数…

M-SOLUTIONS プロコンオープン A - Sum of Interior Angle (灰色, 100 点)

算数の知見がないと、案外難しいかもしれない。 問題へのリンク 問題概要 以上の整数 が与えられます。 正 角形の内角の和を求めてください。 制約 解法 多角形の内角の和の公式を使います。知らない方も、「多角形 内角の和」などと検索すると出て来ると思…

AtCoder AGC 036 A - Triangle (緑色, 400 点)

ちょっと面白い感じの構築問題! 問題へのリンク 問題概要 正の整数 が与えられる。 以下の条件を満たす 3 つの格子点 の組を一つ求めよ。 座標値はすべて 以上 以下の整数値 3 つの格子点からなる三角形の面積を 2 倍すると に一致 制約 考えたこと 仮に 1 …

AtCoder AGC 039 D - Incenters (赤色, 1000 点)

銅色 diff 問題が自力で解けて嬉しい。(修正:赤色になった) 問題へのリンク editorial 問題概要 原点を中心とする半径 1 の円周上に 個の点 がある (偏角が入力として与えられる)。 これらの点からランダムに 3 点選んでできる三角形の内心の座標の期待値を…

AOJ Course CGL_7_C: 外接円 (Circumscribed Circle of a Triangle)

内接円に続いて、外接円も 問題へのリンク 問題概要 二次元平面上に 3 点 A, B, C が与えられる。三角形 ABC の内接円の中心の座標と、半径を求めよ。誤差は まで許容。 制約 座標値の絶対値 考えたこと 内接円よりもやりやすい。 辺 AB の垂直二等分線 辺 B…

AOJ 2385 Shelter (JAG 冬合宿 2010 day4-G) (700 点)

ボロノイ図の応用問題! 問題へのリンク editorials 問題概要 頂点数 の凸多角形があって、その内部に 個の点が与えられる。凸多角形の内部に一様ランダムに点を打つとき、以下の値の期待値を求めよ。 「その点 から 個の点までの距離の最小値」を二乗した値…

AtCoder ABC 168 C - : (Colon) (灰色, 300 点)

余弦定理を使うか、座標を求めるか、、、いずれにしても三角関数の素養を要求する問題。 問題へのリンク 問題概要 時計の時針と分針があって、それぞれ長さは , となっている。 時 分の段階において、時針の先端と分針の先端との距離がどのようになっている…

円と多角形の共通部分の面積 (AOJ Course CGL_7_H)

円と多角形の共通部分の面積を求めるライブラリ、一念発起して整備した!!! サブルーチンとして「円と "線分" の交点を求める」というライブラリが必要となる。 問題へのリンク 問題概要 原点を中心とした半径 の円と、 頂点の多角形が与えられる。これら…

AtCoder ABC 151 F - Enclose All (青色, 600 点)

幾何だ!!!!! そして、こういうので「ギリギリを考える」というのは典型な感じ。 なお、僕は最小包含円のことを知らず、アドホックに解いたけど、ライブラリ貼るだけだったらしい... (その方が計算量も少ない) 他にも、三分探索でも解ける!!! 問題へ…

AtCoder ABC 143 D - Triangles (茶色, 400 点)

教育的ないい問題!!!!! 問題へのリンク 問題概要 本の棒があって、それぞれ の長さをもっている。 このうちの 3 本を選ぶ方法であって、その 3 本で三角形が作れるものは何通あるか? 制約 解法の overview ものすごく色んな解法が考えられる問題だと思…

Tenka1 2019 D - Three Colors (黄色, 600 点)

お 見た目とても面白そう 問題へのリンク 問題概要 要素からなる数列 があたえられる。各要素を「赤」「緑」「青」の三色のいずれかに塗る方法のうち、各色の合計値を として三辺の長さが となるような三角形が存在するようなものを数え上げよ。998244353 で…

Codeforces Global Round 2 E - Pavel and Triangles (R1900)

こういう貪欲は確実に抑えて行きたい 問題へのリンク 問題概要 長さが の線分がそれぞれ 本ずつある。 これらから三角形は最大で何個作れるか? 制約 考えたこと 面白そう!!!!! な量を扱う問題リストにまた 1 問加えられる!!!!! この手の問題では…

AOJ 3056 Equilateral Triangle (RUPC 2019 day2-F)

計算量的な詰めが甘かった。二分探索要らなかった。 問題へのリンク 問題概要 凸な 角形が与えられる。この 角形を完全に含むような正三角形の一辺の長さの最小値を求めよ。 制約 考えたこと 座標系として くらいの大きさまであるので、EPS は くらいがいい…

CS Academy FII Code #1 E - Sugarel’s Garden

にはできたけど、 にできなかった。 問題へのリンク 問題概要 二次元平面上に 点が与えられる。 点から 4 点を選んでできる四角形のうち、内部にちょうど 個の点をもつものすべてを考えたとき、その面積の最小値を求めよ。 制約 どの 3 点も同一直線上にはな…

CS Academy 076 DIV2 D - Pyramids

えーーーーー、どうしてバグに気づかなかった。。。orz 問題へのリンク 問題概要 x 軸上に斜辺を持つような直角二等辺三角形 (三頂点はどれも格子点) が N 個与えられる。N 個の直角二等辺三角形によって被覆される格子点の総数を求めよ。 制約 1 <= N <= 10…

2016 Benelux Algorithm Programming Contest L - Sticky Situation

バチャやりました! vjudge.net L 問題ですが、一番易しい問題です。 問題へのリンク 問題概要 N 個の値 a_1, a_2, ..., a_N が与えられる。 このうちの 3 つをうまく選ぶことで、3 辺の長さがそれらになるような三角形を作ることができるかどうか判定せよ。…

AOJ 0115 Starship UAZ Advance

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0115 三次元幾何 問題概要 三次元空間上で、線分 s と三角形領域 t が与えられる。 s と t とが交点をもつかどうか判定せよ。 解法 まず、sを延長した直線と、tを延長した平面との交点 p を求める…