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;
}
360集团公司氛围 381人发布