torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

幾何

AtCoder Beginner Contest 178, E : Dist Max

問題文 https://atcoder.jp/contests/abc178/tasks/abc178_e 問題概要 二次元空間上に $N$ 個の点があり,$i$ 番目の点の座標は $( x_i, y_i )$ である.異なる 2 点の manhattan 距離の最大値はいくらか? 制約 $2 \leq N \leq 2 \times 10^5$ $1 \leq x_i,…

TopCoder, Single Round Match 668, Division 2, Level 2 : IsItASquare

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=14004&rd=16548 問題概要 平面上の点が 4 個与えられる.これらの点が正方形を成すか? なお,与えられる点は相異なる.

TopCoder, Single Round Match 641, Division 2, Level 2 : TrianglesContainOriginEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13547&rd=16084 問題概要 平面上の点集合が与えられる.この点集合から 3 点を選んで,その 3 点を頂点とする三角形を作ることを考える.点 が三角形の内部に含まれるような 3 点の選び方…

TopCoder, Single Round Match 641, Division 1, Level 1 : TrianglesContainOrigin

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13309&rd=16084 問題概要 平面上の点集合が与えられる.この点集合から 3 点を選んで,その 3 点を頂点とする三角形を作ることを考える.点 が三角形の内部に含まれるような 3 点の選び方…

Codeforces #271, C : Captain Marmot

問題文 http://codeforces.com/contest/474/problem/C 問題概要 直交座標をもつ平面上の点が 個与えられ、 番目の点の座標は である。また、 番目の点は座標 を中心に、反時計回りに [rad] 回転することができる。4 つずつの塊について(すなわち、有効な に…

TopCoder SRM 587, Division 1, Level 2 : TriangleXor

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12528&rd=15699 概要 ある正整数 W があり、( 0, 0 ), ( 0, 1 ), ( W, 0 ), ( W, 1 ) によって張られる XY 平面がある。 この平面上に、( 0, 1 ), ( W, 1 ), ( x, 0 ) (ただし 0 奇数個…

Codeforces 159, C : View Angle

問題文 http://codeforces.com/contest/257/problem/C 概要 二次元平面上の n 個の点の座標が与えられる。 全ての点を内部に含むような角度の内、最小のものを度数法で出力せよ。

AOJ 2423 : Code Art Online

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2423

AOJ 0068 : Enclose Pins with a Rubber Band

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0068 概要 N 本の釘を平板に打ち付け、全ての釘が内部に収まるように輪ゴムを引っ掛けて囲う。 このとき、輪ゴムに接していない釘の本数を出力せよ。