Codeforces Round #432 Div.2 C / Div.1 A - Five Dimensional Points
http://codeforces.com/contest/850/problem/A
問題概要
5次元空間上のN個点が与えられる。この中のある点aについて、異なる点b, cを取ってきたときにab, acのなす角が90度未満となるb, cが存在するとき、aを悪い点と呼び、そうでない場合良い点と呼ぶ。良い点をすべて答えよ。
1 <= N <= 103
解法
Nが33より大きいとき、答えは0である。そうでない場合はN3で全探索すればよい。理由:5次元空間には5個の軸があって25個の象限が存在する。ある点を原点にとったとき同じ象限に存在する点が2点以上あれば、これら3つでつくられる角度は90度未満になる。鳩の巣原理から原点+32象限よりも多くの点が存在すれば必ず同じ象限に2点が存在することになるので、良い点は存在しないことになる。
問題
天才すぎる
コード (D言語)
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop; real angular(int[] x, int[] y, int z[]) { int[] v1 = vec(x, y); int[] v2 = vec(x, z); return acos(product(v1, v2) / sqrt(product(v1, v1) * product(v2, v2))); } real product(int[] v1, int[] v2) { return v1.length.iota.map!(i => v1[i] * v2[i]).sum.to!real; } int[] vec(int[] x, int[] y) { return x.length.iota.map!(i => y[i] - x[i]).array; } void main() { auto N = readln.chomp.to!int; auto P = N.iota.map!(_ => readln.split.map!(to!int).array).array; if (N >= 50) { 0.writeln; return; } const real EPS = 0.0001; auto ans = new bool[N]; fill(ans, true); foreach (i; 0..N) foreach (j; 0..N) foreach (k; 0..N) if (i != j && j != k && k != i && angular(P[i], P[j], P[k]) < PI / 2 - EPS) ans[i] = false; ans.sum.writeln; N.iota.filter!(i => ans[i]).map!(i => (i + 1).to!string).join(" ").writeln; }