Codeforces Round #432

xiaoxiao2021-02-28  15

CF851A Arpa and a research in Mexican wave(水题)

#include <cstdio> #include <cstring> #define N 260 #define ll long long inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } int n,k,t; int main(){ n=read();k=read();t=read(); if(t<=k) printf("%d\n",t); else if(t<=n) printf("%d\n",k); else printf("%d\n",k-(t-n)); return 0; }

CF851B Arpa and an exam about geometry(几何)

a转到b,b转到c,也就是把ab转到bc,首先需要ab是等于bc的。这样就够了么?还要考虑到如果a,b,c是共线的,是无法转到的。(围绕那个点转呢?当然就是ab的中垂线和bc的中垂线的交点啦,如果共线,则没有此交点,也就不能转到)

#include <cstdio> #include <cstring> #define N 260 #define eps 1e-9 #define ll long long inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } inline double abs(double x){return x<0?-x:x;} ll ax,bx,cx,ay,by,cy; int main(){ ax=read();ay=read();bx=read();by=read(); cx=read();cy=read(); if((ax-bx)*(ax-bx)+(ay-by)*(ay-by)==(cx-bx)*(cx-bx)+(cy-by)*(cy-by)){ if(ax+cx==bx*2&&ay+cy==by*2) puts("no"); else puts("yes"); } else puts("no"); return 0; }

CF850A Five Dimensional Points(数学)

先考虑二维的情况。给定一点p,最多能有多少个不同的点满足两两与p构成的角不为锐角?因为都以点p为顶点,那显然最优的情况是360度被分成4个90,也就是说,最多四个点。(官方题解说的这四个点一定分布在不同的象限,我不是很赞同。假设p点所在的象限为I,则我们可以在I中找到两点与p构成直角,然后分别反向延长直角的两条边,必定经过两个另外的象限,分别取一点,即满足。)推广到k维,最多有2*k个。就本题而言,最多10个点能满足题意。也就是说n如果>=12,是一定不满足题意的,直接输出0即可。剩下的情况n很小,可以直接暴力 O(n3) 判断。 在评论中看到的一个想法,跟大家分享一下:算出两两点之间的连线的长度,找到最小的那条线段,记作ab,则好点一定出自a,b。其他点一定都是坏点。为什么呢?首先,如果另一点c和a,b构成了三角形abc,则小边对小角,角C一定是不大于60°的,也就是说c一定是坏点。另一种情况,a,b,c三点一线,因为ab是最短的,所以c一定在a,b同侧,所以c还是个坏点。综上,除了a,b以外的点都是坏点。我们只需判断a,b是否是好点即可。

#include <cstdio> #include <cstring> #include <cmath> #define N 100 inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } struct point{ int x[6]; point operator-(point b){ point res; for(int i=1;i<=5;++i) res.x[i]=x[i]-b.x[i]; return res; } int operator*(point b){ int res=0; for(int i=1;i<=5;++i) res+=x[i]*b.x[i]; return res; } }p[N]; int n,ans[N]; bool good(int x){ for(int i=1;i<=n;++i){ if(i==x) continue; point a=p[i]-p[x];double alen=sqrt(a*a); for(int j=i+1;j<=n;++j){ if(j==x) continue; point b=p[j]-p[x];double blen=sqrt(b*b); if(a*b/(alen*blen)>0) return 0; } }return 1; } int main(){ // freopen("a.in","r",stdin); n=read();if(n>=40){puts("0");return 0;} for(int i=1;i<=n;++i) for(int j=1;j<=5;++j) p[i].x[j]=read(); for(int i=1;i<=n;++i) if(good(i)) ans[++ans[0]]=i; for(int i=0;i<=ans[0];++i) printf("%d\n",ans[i]); return 0; }
转载请注明原文地址: https://www.6miu.com/read-200103.html

最新回复(0)