How to AK ABC259

__vector__ · 2022-07-09 23:04:15 · 个人记录

题外话

赛时因为 B 题被卡了半天才 AC，导致本来会的 D 题没时间做了，最终比赛失败（用小号打的，没有掉 rating）
总结一句话：没先去做 D，\color{red}\text{血亏}

A

模拟

注意：

鬼子出生的时候身高可能不是 1cm，而是 t - x*d，在 t \ge x*d 的时候

B

给定一个点，坐标为 (a,b)，以及一个角度 d(0 \le d \le 360)。求这个点绕原点旋转 d 度之后新的坐标。

注意 cmath 库中的 cos，sin 函数的参数是弧度制的，要将 d 转换成对应的弧度

C

还没做

D

总体思路

将所有相交的圆连边，然后从起始圆（(sx,sy) 所在的圆）出发爆搜，如果能到达终点圆（(tx,ty) 所在的圆），那么就是 Yes，否则 No

细节

• 如何判断两圆是否相交？
  设 (x_1,y_1) 为第一个圆的圆心坐标，(x_2,y_2) 为第二个圆的圆心坐标，设 d 为两个圆的圆心之间的距离，设 r_1,r_2(r_2 \ge r_1) 分别为两个圆的半径。
  若 r_2- r_1 \le d \le r_2+r_1，那么两个圆相交
• 如何避免精度问题
  计算距离的时候，可以将等式两边分别平方，这样就避免了开根。

Code

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    const int maxn=3005;
    vector<int> imap[maxn];
    ll dis2(ll x1,ll y1,ll x2,ll y2)
    {
        return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
    }
    bool islb(ll x1,ll y1,ll r1,ll x2,ll y2,ll r2)
    {
        ll d=dis2(x1,y1,x2,y2);
        if(r2<r1)swap(r2,r1);
        if((r2-r1)*(r2-r1)<=d&&d<=(r2+r1)*(r2+r1))return 1;
        return 0;
    }
    int n;
    struct Circle
    {
        ll x,y,r;
    }cir[maxn];
    bool vis[maxn];
    int sta,en;
    bool dfs(int u)
    {
        if(vis[u])return 0;
        vis[u]=1;
        if(u==en)
        {
            return 1;
        }
        for(int i=0;i<imap[u].size();i++)
        {
            int to=imap[u][i];
            if(dfs(to))
            {
                return 1;
            }
        }
        return 0;
    }
    void main()
    {
        cin>>n;
        ll sx,sy,tx,ty;
        cin>>sx>>sy>>tx>>ty;
        for(int i=1;i<=n;i++)
        {
            cin>>cir[i].x>>cir[i].y>>cir[i].r;
            ll diss=dis2(cir[i].x,cir[i].y,sx,sy);
            if(diss==cir[i].r*cir[i].r)
            {
                sta=i;
            }
            diss=dis2(cir[i].x,cir[i].y,tx,ty);
            if(diss==cir[i].r*cir[i].r)
            {
                en=i;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                if(islb(cir[i].x,cir[i].y,cir[i].r,cir[j].x,cir[j].y,cir[j].r))
                {
                    imap[i].emplace_back(j);
                    imap[j].emplace_back(i);
                }
            }
        }
        if(dfs(sta))
        {
            printf("Yes");
        }
        else printf("No");
    }
}
int main()
{
    Main::main();
    return 0;
}