牛客寒假算法基础集训营 A. 处女座与线性代数(数学+思维)

牛客寒假算法基础集训营 A. 处女座与线性代数(数学+思维)

题目链接：

       先贴一个官方题解

       其实这道题画画图也可以发现一些细节问题。首先要求处女座点的个数，我们肯定是要枚举每一个点，看这个点是否满足和任意两点形成的向量的内积小于0，那么这个过程的时间复杂度是n^，而题目的数据范围是1e4的，显然是过不了的。因此我们可以先看看二维平面的一些性质，如果所形成的向量的夹角是钝角的话，它们的内积就是负的(数学知识)，所以我们就可以枚举每一个点，然后观察是不是这个点和任意两个点相连，所成的角都是负的，当我们在二维平面里枚举了三个点的时候，会发现只会形成一个钝角，所以也就只有一个处女座点，如果是4个点的话，也是只能形成一个处女座点。延申到多维空间，会发现也是满足这个条件的(这个知识一个感性的认知，严谨的证明过程官方题解里有)，这样就得到了一个条件就是不管几个点或者是几维空间，处女座点最多有一个。

       然而只知道这一点并不能解决n^超时的问题，然后我们需要对n有一个限制，还是以二维平面为例，如果我们画了四个点，想要有处女座点存在，就只能有一种画法，处女座点在原点，其余三个点与原点连线，且任意两条线的夹角为120°，那么如果是5个点呢，它们想要形成任意两条线的夹角的最小值最大的话，最多是60/4=90，所以就不会形成处女座点，因此这样k就对n有了范围限制，这也就是n>k2的话就没有处女座点的原因。因为k最大为10，有了限制以后n最大为12，所以n^是可以过的。

AC代码：

#include <bits/stdc.h>
#define ll long long
using namespace std;
int pre[10005][15];
int T,n,k;int main()
{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,&pre[i][j]);}}vector<int> v;if(n > k  2){puts(0);continue;}for(int i=0;i<n;i){bool flag = true;for(int j=0;j<n-1;j){if(i == j)continue;for(int m=j1;m<n;m){if(i == m)continue;ll ans = 0;for(int l=0;l<k;l){ans = (pre[j][l] - pre[i][l]) * (pre[m][l] - pre[i][l]);}if(ans >= 0){flag = false;break;}}}if(flag){v.push_back(i);}}printf(%d\n, v.size());for(int i=0;i<v.size();i){for(int j=0;j<k;j){printf(%d ,pre[v[i]][j]);}puts();}}return 0;
}