codeforces 851 #432 div2 C Five Dimensional Points

Problem

codeforces.com/contest/851/problem/C

Preference

Codeforces Round #432 editorial
Codeforces Round #432 (Div. 2) - C - Five Dimensional Points

Meaning

有 n 个五维空间里的点，构成点集。对于任意一个点 a，如果点集中存在任意两个不相同的点 b 和 c（也不和 a 相同），使得向量 ab→ 和 ac→ 的夹角小于 90∘ ，则 a 是bad，否则 a 是good。输出所有good的点。

Analysis

在二维平面中，对任意一个点，如果它是good，那么平面中除了它之外最多只能有另外 4 的点，分别在它的：x 轴正半轴方向、负半轴方向、y 轴正半轴方向、负半轴方向上（反正就是 4 个直角，可以把坐标系旋到这种分布）。再多一个点，必然会形成小于 90∘ 的情况。
到三维空间，就再加多两个点：z 轴正、负半轴方向上。
以此类推，五维空间里最多就只能存在另外 10 个点（加上good点自己 11 个），否则一个good点都没有。
题目判夹角小于 90∘ 是用 arccos(x⃗ ⋅y⃗ |x⃗ |⋅|y⃗ |) 。因为向量夹角范围是 [0,π] ，观察arccos在 [0,π] 的函数图像可以发现，夹角小于 90∘ 等价于 x⃗ ⋅y⃗ >0 。

Code

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1000, D = 5;

int p[N][D]; // 点
int vec[N][N][D]; // vec[i][j]：向量 ij
int ans[N]; // 答案序列
bool ok[N]; // good 点为 true
bool vis[N][N]; // vec[i][j] 是否计算过

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < D; ++j)
            scanf("%d", p[i]+j);
    // 多于 11 个点 -> 必无 good 点
    if(n > 11)
    {
        puts("0");
        return 0;
    }
    memset(vis, false, sizeof vis);
    memset(ok, true, sizeof ok);
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
        {
            if(i == j)
                continue;
            // 计算向量 ij 和 ji
            if(!vis[i][j])
            {
                vis[i][j] = vis[j][i] = true;
                for(int k = 0; k < D; ++k)
                {
                    vec[i][j][k] = p[j][k] - p[i][k];
                    vec[j][i][k] = -vec[i][j][k];
                }
            }
            // 判点 i 是否为 good
            for(int k = 0, dot; ok[i] && k < j; ++k)
            {
                dot = 0; // 向量 ij 和 ik 的点积
                for(int l = 0; l < D; ++l)
                    dot += vec[i][k][l] * vec[i][j][l];
                // 点积大于 0 -> 小于 90 度 -> bad
                if(dot > 0)
                    ok[i] = false;
            }
        }
    int cnt = 0;
    for(int i = 0; i < n; ++i)
        if(ok[i])
            ans[cnt++] = i + 1;
    printf("%d\n", cnt);
    for(int i = 0; i < cnt; ++i)
        printf("%d%c", ans[i], i == cnt - 1 ? '\n' : ' ');
    return 0;
}