CF850A Five Dimensional Points 题解
2021/10/11 23:18:28
本文主要是介绍CF850A Five Dimensional Points 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Link.
Codeforces
Luogu
Description.
给定 \(n\) 个五维坐标系中的点,找到所有点 \(A\),使得
- \(\forall B,C\in S,<\overrightarrow{AB},\overrightarrow{AC}>\ge \frac{\pi}{2}\)
Solution0.
\(O(n^3)\) 暴力直接 AC。
Solution1.
假设我们要判断 \(A\) 点是否可行。
考虑以 \(A\) 点为坐标原点建立新的直角坐标系。
把平面分成了 \(2^5=32\) 个象限,如果任意两个点在同一个象限内,则角度必 \(<\frac{\pi}2\)。
所以当 \(n>33\) 时必然有解。
复杂度 \(O(n)\)
Solution2.
考虑三个点构成三角形,必然存在至少两个角是锐角。
考虑维护一个 queue
,每次取出队顶然后判断以下,至少可以删掉两个点。
复杂度 \(O(n)\)。
Coding1.
点击查看代码
//是啊,你就是那只鬼了,所以被你碰到以后,就轮到我变成鬼了{{{ #include<bits/stdc++.h> using namespace std;typedef long long ll; template<typename T>inline void read(T &x) { x=0;char c=getchar(),f=0; for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1; for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48); f?x=-x:x; } template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}} #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") const int N=1005;int n; struct $ { int a,b,c,d,e; inline $ operator-($ x) {return ($){a-x.a,b-x.b,c-x.c,d-x.d,e-x.e};} inline int operator*($ x) {return a*x.a+b*x.b+c*x.c+d*x.d+e*x.e;} }a[N]; int main() { read(n);if(n>=50) {return puts("0"),0;} for(int i=1;i<=n;i++) read(a[i].a,a[i].b,a[i].c,a[i].d,a[i].e); vector<int>v;for(int i=1;i<=n;i++) { char fg=1; for(int x=1;x<=n&&fg;x++) if(x^i) for(int y=x+1;y<=n&&fg;y++) if(y^i) if((a[x]-a[i])*(a[y]-a[i])>0) {fg=0;break;} if(fg) v.push_back(i); }printf("%d\n",(int)v.size()); for(auto x:v) printf("%d ",x); return 0; }
这篇关于CF850A Five Dimensional Points 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享