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;
}