题解 P9720【[EC Final 2022] Map】

· · 题解

[EC Final 2022] Map

看着挺吓人的一道计算几何，其实写起来挺简单（？

首先最优的方案一定是先进行若干次连续的 f，然后走一小段，再进行若干次连续的 f^{-1}，这样一定是最优的。

为什么呢？假设在走了一段路之后再进行 f，那么这段路肯定放在 f 之后走更优，因为地图中的路程一定更短。先 f^{-1} 再走的情况同理。

所以只需要枚举 f 和 f^{-1} 的次数，由于 n 很小，所以可以 \mathcal{O}\big(n^2\big) 枚举。

接下来重点在于如何优雅地实现 f，不妨利用矩形的正交性，以矩形的左下角为原点建系：

设当前坐标在 DAB 坐标系下对应的向量为 \mathbf{u}，我们只需要把 \mathbf{u} 沿着 AD 和 AB 进行分解，然后把坐标系变换到 HEF，再按照两个矩形的相似比进行伸缩变换就可以合成 \mathbf{v}。

具体变换可以用点乘实现，可以参考代码。

时间复杂度 \mathcal{O}(n^2)。

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef long double ld;
using namespace std;
const int N=110,M=10010,INF=0x3f3f3f3f;
const ld inf=2e18;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline void swap(int &x,int &y){x^=y^=x^=y;}
struct node{
    ld x,y;
    node(ld xx=0,ld yy=0){x=xx,y=yy;}
    void in(){scanf("%Lf%Lf",&x,&y);}
}A[5],B[5],S,T;

node operator +(node a,node b){return node(a.x+b.x,a.y+b.y);}
node operator -(node a,node b){return node(a.x-b.x,a.y-b.y);}
ld operator *(node a,node b){return a.x*b.x+a.y*b.y;}
ld operator ^(node a,node b){return a.x*b.y-a.y*b.x;}

node operator *(ld x,node a){return node(x*a.x,x*a.y);}

ld sqr(ld x){return x*x;}
ld dis(node a,node b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}

int _,n,k;
ld ans;

node f(node p){
    node ao=A[1],ai=A[4]-A[1],aj=A[2]-A[1];
    node bo=B[1],bi=B[4]-B[1],bj=B[2]-B[1];
    p=node(((p-ao)*ai)/(ai*ai),((p-ao)*aj)/(aj*aj));
    return bo+p.x*bi+p.y*bj;
}
void solve(){
    ans=inf;
    for(int i=1;i<=4;i++)A[i].in();
    for(int i=1;i<=4;i++)B[i].in();
    S.in();T.in();
    scanf("%d%d",&k,&n);
    node u=S;
    for(int i=0;i<=n;i++,u=f(u)){
        node v=T;
        for(int j=0;i+j<=n;j++,v=f(v))
            ans=std::min(ans,dis(u,v)+k*(i+j));
    }
    printf("%.10Lf\n",ans);
}
int main(){
    scanf("%d",&_);
    while(_--)solve();
    return 0;
}