hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング 条件を満たす3頂点を答えよ x,y座標が[0,3000]に収まる できる三角形の外周がperimeterであり、面積がarea 解法 どのような三角形も回転や平行移動をすれば、(0,0)を通るようにできる。 なので、1つの頂点は(0,0)で他の2頂点を考えよう。 他の2頂点は外周が整数であるため、(0,0)からの長さも整数になる必要がある。 [0,3000]の範囲で(0,0)からの長さが整数となる点はそんなに多くない（10^4くらい）。 なので、これを全部探し、そのうち２つを、他の2頂点として採用できるか考える。一辺がx軸、y軸に平行になると仮定するのは以下で落ちる。 area=252, pe… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2018%2F10%2F01%2F035343" title="FindThePerfectTriangle [TopCoder SRM 738 Div1 Easy] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-10-01 03:53:43 rich https://blog.hamayanhamayan.com/entry/2018/10/01/035343 1.0 100%