T637074 题解

_j_o_k_e_r_ · 2025-07-22 09:35:55 · 题解

本题本来要由 xwx123456 提供一道随机化题目（原因众所周知），但 xwx123456 有其他事，改为由 _j_o_k_er 提供，仍有随机化做法，预估难度为绿。

注意到题目限制比较灵活（改了又改），很难统一构造方案，所以我们充分发扬人类智慧，用随机化，把点随机出来，但也不是乱随机，是有一定道理的随机。

前 n-1 个点要求比较少，只有一个限制：总长不超过 C。举个例子，n=3,C=12，设当前路程和为 c，如下图：

刚开始什么也没有，c=0，科比从家出发。现在随机出来一个点 (3,0)：

此时 c=\sqrt{(0-0)^2+(3-0)^2}=3，我们再随机出来一个点 (5,0)。

此时 c=3+\sqrt{(5-0)^2+(3-0)^2}=3+\sqrt{34}\approx 8.831，我们要求 C=12，并没有超过，但这时候我们已经知道这样不行了。因为最后要回到原点，两点之间，线段最短，所以回到原点至少需要走 5，即最终 c \ge 8.831+\sqrt{(5-0)^2+(0-0)^2}，即 c \ge 13.831，这不满足 C=12 的要求，所以我们重新随机一个点 (3,3)：

此时 c=3+\sqrt{(3-3)^2+(3-0)^2}=6，(3,3) 与原点之间的距离为 \sqrt{(3-0)^2+(3-0)^2}=3\sqrt{2}\approx 4.243，最终 c \ge 6+4.243=10.243，符合要求，继续。

重点：此时已经有了 2 个点，再有 1 个点就够了，设最后一个点的坐标为 (a,b)，倒数第二个点的坐标为 (x,y)，dis(a,b,x,y) 表示坐标系上 (a,b) 与 (x,y) 之间的距离，最后一个点需要满足：

其中 Eps 为题目给的极小值 10^{-4}。因为 Eps 极小，所以我们干脆让上面的一堆等于 C，Eps 的误差留给浮点数的计算。

注意到 c,C,x,y 为已知数，有 a,b 两个未知数，只有一个方程，所以有无数组解，我们只需要其中一组或两组（原因见下）解就够了，所以不妨令 a=0，解出 b，再令 b=0，解出 a，就有两组解了：

注意到有分数，分母不能为 0，所以如果 2y-2k=0 就用第二组解，不然就用第一组解。

带入上面的例子 x=3,y=3,C=12,c=6 得 a=0,b=3：

然后就可以敲代码了：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<random>
#include<queue>
#include<ctime>
#include<map>
#define intu unsigned long long
#define intt long long
#define dlel long double
#define dle double
using namespace std;
const int Imax=0x7fffffffL;
const long long LLmax=0x7fffffffffffffffLL;
const dle Eps=1e-4;
mt19937 _rand(time(0));
dle Mod;
int n;
dle C;
dle c;
dle a,b,x,y;
dle dis(dle x1,dle y1,dle x2,dle y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}//两点间距离
int cnt;
map<dle,map<dle,bool> > mp;//记录某个点是否走过
dle Rand(dle p)//生成[0,p] 的浮点随机数
{
    int m=_rand()%3;
    dle res=_rand()/pow(10,m); 
    return res-((int)(res/p))*p;
}
int main()
{
    scanf("%d%lf",&n,&C);
    n++;
    Mod=2*sqrt(C/3.14);//玄学？
    cnt=1;
    mp[0][0]=1;
    while(1)
    {
        if(cnt==n-1)
        {
            dle k=C-c;
            a=b=0;
            if(fabs(x-k)<=Eps) b=(x*x+y*y-k*k)/(2*y-2*k); 
            else a=(x*x+y*y-k*k)/(2*x-2*k);
            c+=dis(x,y,a,b)+dis(a,b,0,0);
            printf("%lf %lf",a,b);
            return 0;
        }
        a=b=Mod-0.001;
        while(1)
        {
            a=Rand(a-0.001);
            b=Rand(b-0.001);
            if(cnt)
            {
                if(!a&&!x)//直走或调头
                {
                    a=b=Mod-0.001;
                    continue;
                }
                else if(fabs(b/a-y/x)<=Eps)//直走或调头
                {
                    a=b=Mod-0.001;
                    continue;
                }
            }
            if(c+dis(x,y,a,b)+dis(a,b,0,0)<C&&!mp[a][b])
            {
                mp[a][b]=1;
                break;
            }
        }
        printf("%lf %lf\n",a,b);
        c+=dis(x,y,a,b);
        x=a;
        y=b;
        cnt++;
    }
    return 0;
}

当然有其它做法，你完全可以把它当数学题做，用到三角函数，比较考验思维和数学功底，但难度还是在绿左右。