P7069: Another NOILHSX 2024 D1T1

035966_L3 · 2024-07-13 13:33:13 · 题解

本题是 NWRRC 2014 Problem J。

本题在 CodeForces 上有提交通道：Gym 100531J。

为什么就连联合省选都开始搬原题了啊，这么没素质的吗！

很明显，飞机的位移分为两部分：风带来的位移和飞机自身的位移。因此，我们可以先让飞机在无空速的情况下随风移动 k 秒，排除风速的影响。

移动结束后，剩下来的路程就要靠飞机的空速来弥补了。很明显，飞机在 k 秒内最多可以靠空速移动 k \cdot v_{\max} 的距离，因此只需要计算一下剩下来的路程长度，并和 k \cdot v_{\max} 进行比较就可以了。

至于构造……很明显，设剩下来的路程是 \bm {X}=(a,b)，那么将每秒的空速都设成 \dfrac{\bm X}{k}=(\dfrac{a}{k},\dfrac{b}{k}) 就可以了。

AC Code：

#include<bits/stdc++.h>
using namespace std;
int a[10012],b[10012],c[10012];
int main()
{
    int sx,sy,fx,fy;
    cin>>sx>>sy>>fx>>fy;
    int tx=sx,ty=sy;
    int n,k,v;
    cin>>n>>k>>v;
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i]>>c[i];
    a[n+1]=k;
    int p=0;
    for(int i=0;i<=k-1;i++)
    {
        if(a[p+1]==i) p++;
        tx+=b[p],ty+=c[p];
    }
    long double dis=sqrtl(1ll*(fx-tx)*(fx-tx)+1ll*(fy-ty)*(fy-ty));
    if(dis>k*v)
    {
        puts("No");
        return 0;
    }
    puts("Yes");
    long double mx=(fx-tx)/1.0/k,my=(fy-ty)/1.0/k;
    long double ssx=sx,ssy=sy;
    p=0;
    for(int i=0;i<=k-1;i++)
    {
        if(a[p+1]==i) p++;
        ssx+=b[p],ssy+=c[p];
        ssx+=mx,ssy+=my;
        cout<<fixed<<setprecision(50)<<ssx<<' '<<ssy<<endl;
    }
    return 0;
}