自动搬运

查看原文

来自洛谷，原作者为

	Diaоsi Enemy of God

搬运于2025-08-24 22:51:09，当前版本为作者最后更新于2024-05-21 17:24:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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