竞赛讨论区 > I题工具人求助dalao
头像
RandolphJ
发布于 2020-03-02 09:34
+ 关注

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;
}

全部评论

(3) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐