I题工具人求助dalao
初中蒟蒻瑟瑟发抖qwq。。
不知道本题需要什么数学知识(我尽量尝试理解)?我简单了解了一下弧度,dalao能解释一下下面这个程序(来自Marco.L.T.的AC代码)的思路是怎么做的吗?39行的otg、还有那个加减2pi是什么意思?
如果dalao有更好的思路也可以发一下你的代码给我,谢谢qwq!
#include <bits/stdc++.h> #define eps 1e-9 #define ll long long #define pb push_back #define mp make_pair #define fi first #define se second #define mod 1000000007 using namespace std; int a[100005],n; struct node { double x,y,l,r; } p[505]; double pl[505],pr[505]; double maxr[505]; bool vis[505]; inline bool cmp(node a,node b) { return a.l<b.l; } int main () { int i,j,k,T; scanf ("%d",&T); while (T--) { int cnt=0; double d; double pi=acos(-1.0); scanf ("%d%lf",&n,&d); for (i=1; i<=n; i++) { int x,y; scanf ("%d%d",&x,&y); p[++cnt].x=x; p[cnt].y=y; double dis=sqrt(p[cnt].x*p[cnt].x+p[cnt].y*p[cnt].y); if (dis<=d) { cnt--; continue; } double si=d/dis; double otg=si/sqrt(1-si*si),t=atan(otg); double tg=atan2(p[cnt].y,p[cnt].x); p[cnt].l=tg-t; p[cnt].r=tg+t; while (p[cnt].l<0) { p[cnt].l+=2.0*pi; p[cnt].r+=2.0*pi; } while (p[cnt].l>2.0*pi) { p[cnt].l-=2.0*pi; p[cnt].r-=2.0*pi; } } sort(p+1,p+cnt+1,cmp); int ans=max(1,cnt); for (i=1; i<=cnt; i++) { int res=0,co=0; memset(vis,0,sizeof(vis)); for (j=i; j<=cnt; j++) { pl[++co]=p[j].l; pr[co]=p[j].r; } for (j=1; j<i; j++) { pl[++co]=p[j].l+2.0*pi; pr[co]=p[j].r+2.0*pi; } int pos=1,nc=0; maxr[cnt]=pr[cnt]; for (j=cnt-1; j>=1; j--) maxr[j]=min(maxr[j+1],pr[j]); while (pos<=cnt) { double no=maxr[pos]; while (pos<=cnt&&pl[pos]<=no) pos++; nc++; } if (nc<ans) ans=nc; } printf ("%d\n",ans); } return 0; }