https://ac.nowcoder.com/acm/contest/329/A

题解：

std

作者：儒生雄才1
链接：https://ac.nowcoder.com/discuss/152781
来源：牛客网
 

我们将列举出本题所使用到的结论：

1.处女座点的数量最多为 1

证明：

2. 若K维空间一个点集{P1,P2,⋯,PnP1,P2,⋯,Pn}存在处女座点，则𝑵≤𝑲+𝟐≤𝟐𝑲+𝟏

严格的证明需要利用高等代数。但是利用数学归纳法或线性代数方法证明同条件下证明𝑁≤2𝐾+1是显然的。 （提示：将处女座点的定义弱化为向量夹角为钝角或直角后即可证明）

综上所述，若𝑁>𝐾+2则直接输出0，否则暴力检查即可。由于𝐾≤10，用𝑁>2𝐾+1判断也是可以的。
时间复杂度𝑂(𝐾^3)。

#include <cstdio>
#include <vector>
 
using namespace std;
 
int pt[10005][15];
int n, k;
 
int dot(int p, int p1, int p2) {
    int ans = 0;
    for (int i = 0; i < k; ++i)
        ans += (pt[p1][i] - pt[p][i]) * (pt[p2][i] - pt[p][i]);
    return ans;
}
 
int main(int argc, char* argv[]) {
 
    int kase = 0;
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d", &n, &k);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < k; ++j)
                scanf("%d", &pt[i][j]);
        }
 
        int ans = -1;
        if ((k > 1 && n <= 2 * k) || (k == 1 && n <= 3)) {
            for (int p1 = 0; p1 < n; ++p1) {
                bool flag = true;
                for (int p2 = 0; p2 < n; ++p2) {
                    for (int p3 = 0; p3 < n; ++p3) {
                        if (p1 == p2 || p1 == p3 || p2 == p3)
                            continue;
                        if (dot(p1, p2, p3) >= 0) {
                            flag = false;
                            break;
                        }
                    }
 
                    if (!flag)
                        break;
                }
 
                if (flag) {
                    ans = p1;
                    break;
                }
            }
        }
 
        if (ans == -1)
            puts("0");
        else {
            puts("1");
            for (int i = 0; i < k; ++i) {
                if (i > 0)
                    putchar(' ');
                printf("%d", pt[ans][i]);
            }
            putchar('\n');
        }
    }
    return 0;
}