codeforces 850 A

A. Five Dimensional Points

introduction

在n個點中，是否存在一個點，與另外任意兩個點連成的向量，為銳角

method

首先在2維的空間中，要讓角不為銳角，最多只能存在5個點(四個向量) 。鴿巢原理。在k維空間中，最多只能存在2k+1個節(jié)點。k=5時，最多只能存在11個節(jié)點。所以:

• 輸出0，如果節(jié)點數(shù)大于11
• 枚舉，如果節(jié)點數(shù)小于等于10

tips

成角的向量不能隨意交換向量的兩個端點

節(jié)點數(shù)=向量數(shù)+ 1

鴿巢原理是非常有用

reference

http://codeforces.com/blog/entry/54317
https://blog.csdn.net/Fusheng_Yizhao/article/details/78557741
鴿籠原理 謝聰智

code

#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<string> #include<vector> #include<cmath> #include<map> #include<istream> #include<ostream> #define DEBUG(x) cout<<#x<<" = "<<x<<endl #define pi acos(-1) using namespace std; const int MAXN=1e3+10; struct point{int a[5];point(){memset(a,0,sizeof(a));}friend istream & operator>>(istream &in,point &p){for(int i=0;i<5 ;i++ ){in>>p.a[i];}return in;}friend ostream &operator<<(ostream &out,const point &p){for(int i=0;i<5 ;i++ ){out<<p.a[i]<<" ";}return out;} }; typedef point vec; inline vec mkvec(point &p1,point &p2) {vec v;for(int i=0;i<5 ;i++ ){v.a[i]=p2.a[i]-p1.a[i];}return v; } int n; point pts[MAXN]; int dot(vec &p1,vec &p2) {int rt=0;for(int i=0;i<5 ;i++ ){rt+=p1.a[i]*p2.a[i];}return rt; } ///根據(jù)鴿巢原理可以大幅度降低復(fù)雜度 ///向量是有方向的 int main() { // freopen("in.txt","r",stdin);cin>>n;for(int i=1;i<=n ;i++ ){cin>>pts[i];}vector<int>ans;if(n<3){for(int i=1;i<=n ;i++ ){ans.push_back(i);}}else if(n<=11)for(int i=1;i<=n ;i++ ){vector<vec>v;for(int j=1;j<=n ;j++ ){if(i!=j)v.push_back(mkvec(pts[i],pts[j]));}bool ok=true;for(int k=0;k<v.size() ;k++ ){for(int u=k+1;u<v.size() ;u++ ){if(dot(v[k],v[u])>0)ok=false;}}if(ok)ans.push_back(i);}cout<<ans.size()<<endl;for(int i=0;i<ans.size() ;i++ ){cout<<ans[i]<<endl;} }

轉(zhuǎn)載于:https://www.cnblogs.com/MalcolmMeng/p/10195067.html

總結(jié)

以上是生活随笔為你收集整理的codeforces 850 A的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。