[EC Final 2022] Map

GitHub跳转原题关系图返回列表

最优路线可化为对 s、t 各连续做若干次「公园→地图」收缩传送后走直线，枚举两个次数使 a+b≤n 即可，O(n²)。

OJ: luogu

题目 ID: P9720

难度:省选/NOI-

标签:计算几何相似变换枚举数学

创建: 2026-10-02 15:23

更新: 2026-10-03 12:51

形式化题目

平面上给定两个矩形：公园 $P$ 与地图 $M$ ， $M$ 是 $P$ 的相似图形且完全落在 $P$ 内。第 $i$ 个地图角点对应第 $i$ 个公园角点，因此存在相似变换 $f:M\to P$ ，其相似比 $r=\dfrac{|f(a)-f(b)|}{|a-b|}\geqslant 1$ （地图不小，故 $f$ 是放大）。令 $g=f^{-1}$ 为反向收缩。

Mio 位于公园内的点 $x$ 时，可以选择：不动，或传送到 $g(x)\in M$ （公园 $\to$ 地图）。若 $x$ 同时落在地图上，还可以传送到 $f(x)\in P$ （地图 $\to$ 公园）。每传送一次耗时 $k$ 秒，最多传送 $n$ 次；步行速度为 $1$ 单位每秒，可在平面内任意行走。

给定 $s,t$ （均在 $P$ 内），求从 $s$ 到 $t$ 所需的最小总时间。注意地图可能被翻转，故 $f$ 允许带反射。

正解

思路

先看传送能到达哪里。一次传送把点沿相似变换 $f$ 或 $g$ 搬一次，其中 $g$ 把公园收缩成地图，是个「变小」的映射。走路则不改变位置关系，只产生欧氏距离。

关键观察一：连续的 $f$ 与 $g$ 相邻出现时，必定浪费。

$f$ 与 $g$ 互为逆映射，所以对合法位置有 $g(f(x))=x$ 、 $f(g(y))=y$ 。若路线中出现了 $f$ 紧接着 $g$ （或反过来），这一对会回到原处，白白花掉 $2k$ 秒。把它们删掉，路线其余部分不变，只会更优。所以最优路线的传送段中， $g$ 与 $f$ 不会交替，一定是「先若干个 $g$ 、再若干个 $f$ 」，或相反的「先若干个 $f$ 、再若干个 $g$ 」。

关键观察二：走路应当尽量晚走。

$g$ 是收缩映射，对任意两点都有 $|g(a)-g(b)|=\dfrac{|a-b|}{r}\leqslant |a-b|$ 。因此把一段步行挪到某个 $g$ 之后，这段位移只会变短或不变，不可能变长。

把两条观察合起来：最优路线形如

s \xrightarrow{\ g^{a}\ } s_a \xrightarrow{\ \text{步行}\ } u \xrightarrow{\ f^{c}\ } t,

即先对 $s$ 做 $a$ 次收缩，再走一段直线，最后做 $c$ 次放大到达 $t$ ，其中 $a+c\leqslant n$ 。

最后的放大段可以直接反过来理解：既然 $f^{c}(u)=t$ ，就有 $u=g^{c}(t)$ 。于是整条路线等价于

\text{对 } s \text{ 做 } a \text{ 次 } g,\quad \text{对 } t \text{ 做 } b \text{ 次 } g,\quad \text{再走直线},

其中 $a+b\leqslant n$ 。由对称性，先放大后收缩的情况完全一样（ $a$ 与 $b$ 互换，距离对称）。

于是答案就是

\min_{a+b\leqslant n}\ \Bigl(\bigl|g^{a}(s)-g^{b}(t)\bigr| + k(a+b)\Bigr).

因为 $n\leqslant 100$ ，直接枚 $a,b$ 两层循环即可，每层把点做一次 $g$ 。

如何实现一次 $g$ （公园 $\to$ 地图）。

两个矩形都是矩形，所以从同一个角点出发的两条邻边互相垂直，可以当正交基用。设公园角点依次为 $A_1\dots A_4$ 、地图角点为 $B_1\dots B_4$ ，且 $A_i$ 对应 $B_i$ 。取

A_1,\quad u=A_4-A_1,\quad v=A_2-A_1,

对公园内任意点 $p$ ，把它在这组基下分解：

\alpha=\frac{(p-A_1)\cdot u}{u\cdot u},\qquad \beta=\frac{(p-A_1)\cdot v}{v\cdot v}.

由于地图与公园相似且对应边一一对应，同样的系数配在地图的正交基上就得到像点：

g(p)=B_1+\alpha\,(B_4-B_1)+\beta\,(B_2-B_1).

这组点积写法自动处理了旋转与翻转，不需要单独讨论地图是否倒放；也不需求出相似比 $r$ 。

另外，每一步枚举都让 $a+b\leqslant n$ ，所以传送次数约束天然满足； $a=b=0$ 的项就是「完全不传送、直接走过去」。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-03 12:45
 */
// main.cpp：P9720 [EC Final 2022] Map 正解。
//
// 核心结论：最优路线一定可以写成
//   从 s 连续做 a 次“公园 -> 地图”传送到达 s'；
//   从 t 连续做 b 次“公园 -> 地图”传送到达 t'；
//   再从 s' 沿直线走到 t'，其中 a + b <= n。
//
// 为什么只用“公园 -> 地图”这一个方向：
//   1) 走路放在传送中间不如挪到最后。地图比公园小，把中间那段路挪到
//      最后走只会更短（题解中有完整证明）。
//   2) “地图 -> 公园”之后再“公园 -> 地图”会原样回到出发点，白花 2k 秒，
//      所以最优序列里不会出现这种反复。
//
// 于是只要枚举 a、b，每次“公园 -> 地图”就是这个相似变换的逆，
// 直接把点按固定比例收缩，复杂度 O(n^2)。
#include <bits/stdc++.h>
using namespace std;

const long double INF = 1e30L;

// 二维点 / 向量
struct Point {
    long double x, y;
};

Point operator+(Point a, Point b) { Point c; c.x = a.x + b.x; c.y = a.y + b.y; return c; }
Point operator-(Point a, Point b) { Point c; c.x = a.x - b.x; c.y = a.y - b.y; return c; }
Point operator*(long double t, Point a) { Point c; c.x = t * a.x; c.y = t * a.y; return c; }

// 点积
long double dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }

Point park[5]; // 公园的四个角，下标 1..4
Point mp[5];   // 地图的四个角，下标 1..4
Point s, t;    // 起点、终点，均在公园内
int k, n;      // 每次传送耗时、传送次数上限

long double dist(Point a, Point b) {
    long double dx = a.x - b.x;
    long double dy = a.y - b.y;
    return sqrtl(dx * dx + dy * dy);
}

// 公园中的点 p 传送到地图上的对应点，即题面中的 f^{-1}。
// 公园、地图都是矩形，所以 park[1] 出发的两条边 park[4]-park[1] 与
// park[2]-park[1] 相互垂直：先把 p 在这组正交基下分解，再用地图的
// 对应两条边还原即可。第 i 个地图角对应第 i 个公园角，故基向量也一一对应。
Point park_to_map(Point p) {
    Point o1 = park[1], e1 = park[4] - park[1], e2 = park[2] - park[1];
    Point o2 = mp[1],   f1 = mp[4] - mp[1],     f2 = mp[2] - mp[1];
    long double c1 = dot(p - o1, e1) / dot(e1, e1);
    long double c2 = dot(p - o1, e2) / dot(e2, e2);
    return o2 + c1 * f1 + c2 * f2;
}

void solve() {
    for (int i = 1; i <= 4; i++) {
        cin >> park[i].x >> park[i].y;
    }
    for (int i = 1; i <= 4; i++) {
        cin >> mp[i].x >> mp[i].y;
    }
    cin >> s.x >> s.y >> t.x >> t.y;
    cin >> k >> n;

    long double ans = INF;
    Point u = s;                                    // 对 s 做 a 次传送
    for (int a = 0; a <= n; a++) {
        Point v = t;                                // 对 t 做 b 次传送
        for (int b = 0; a + b <= n; b++) {
            long double cost = dist(u, v) + (long double)k * (a + b);
            if (cost < ans) ans = cost;
            v = park_to_map(v);
        }
        u = park_to_map(u);
    }
    cout << fixed << setprecision(10) << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) solve();

    return 0;
}

复杂度

每个测试点枚举 $O(n^2)$ 个 $(a,b)$ 组合，每次做 $O(1)$ 次点积与开方；总时间复杂度 $O(Tn^{2})$ ，空间 $O(1)$ 。

总结

本题的难点不在计算几何的实现，而在把连续的最优路线压缩成有限种结构：

相邻的 $f$ 与 $g$ 会互相抵消，最优序列不会让两个方向交替；
$g$ 是收缩映射，任何步行段挪到收缩之后都只会更短。

两条一合并，路线就被固定成「对 $s$ 收缩若干次、对 $t$ 收缩若干次、然后走直线」，用 $O(n^2)$ 枚举即可。实现上只需用矩形邻边构造正交基做点积分解，就能一次性处理旋转和翻转。

P9720 [EC Final 2022] Map

题目描述

It is a famous math fact that if you drop a map of a park completely inside the park, then there exists a point on the map which overlays with the point it represents.

Mio likes this fact a lot so she drops a map of her favorite park completely inside the park. The park $P$ can be represented by a rectangle. A map of the park is just a smaller (or equal) version of the park printed on paper. The map is similar to the original rectangle. Each point on the map corresponds to a point in the park by the similarity transformation.

We can define a map formally: A map is a rectangle $M$ (of smaller or equal size) together with a positive real number $r$ and a bijective function $f:M \rightarrow P$ satisfying

For every pair of different points $a, b\in M$ , $|f(a)-f(b)|/|a-b|=r$ .

$|x-y|$ represents the Euclidean distance between points $x$ and $y$ .

Like in many games, Mio can teleport using the map. Precisely, when Mio is at some point $x$ on the map (including the boundary), she may teleport to the corresponding point $f(x)$ in the park. She may also choose not to teleport. The reverse is also true. When she is at point $y$ in the park (including the boundary), she may teleport to the point $f^{-1}(y)$ on the map representing her current location. And she may also choose not to teleport.

Mio can teleport at most $n$ (and at least $0$ ) times. Each teleport takes $k$ seconds. Mio can also walk on her foot at a speed of $1$ unit per second.

Given two points $s$ and $t$ , find the minimum time Mio needs to reach $t$ from $s$ .

Each teleport can be in any direction (from the map to the park, or from the park to the map). The map may be placed upside down. Since the map is inside the park, it is possible that Mio is on the map and in the park simultaneously. In this case, she may teleport in either direction.

For example, in the following figure, the park is $ABCD$ , and the map is $A'B'C'D'$ . When Mio is inside the map, she is on the map and in the park simultaneously. When she is at point $D'$ , she can teleport from the map to the park (reaching $D$ ), and from the park to the map (reaching $D^{\prime\prime}$ ).

输入格式

The first line contains a single integer $T$ ( $1\le T\le 100$ ) denoting the number of test cases.

For each test case, the first line contains the $4$ corners of the rectangle representing the park. The corners are given in clockwise or counterclockwise order. It is guaranteed that the $4$ corners are distinct.

The second line contains the $4$ corners of the rectangle representing the map. The $i$ -th corner of the map corresponds to the $i$ -th corner of the park for all $1\le i\le 4$ . Note that you can figure out whether the map is placed upside down or not by the order of the corners. The corners are given in clockwise or counterclockwise order. It is guaranteed that the map is inside the park. (The boundary of the map may intersect with the boundary of the park at $1$ or more points.) It is guaranteed that the map is valid, i.e., there is a positive real number and a bijective function from the map to the park satisfying the definition above.

The third line contains two points $s$ and $t$ . It is guaranteed that $s$ and $t$ are inside (or on the boundary of) the park.

The fourth line contains two integers $k, n$ ( $0\le k\le 2\times 10^6, 0\le n\le 100$ ), the time each teleport needs, and the maximum number of teleports.

Each point in the input is represented by a pair of integers whose absolute values are no more than $2\times 10^6$ . Integers are separated by single spaces.

输出格式

For each test case, output one number representing the answer in one line. Your answer is considered correct if its absolute or relative error does not exceed $10^{-9}$ .

输入输出样例 #1

输入 #1

text

1
2
3
4
5
6
7
8
92
0 0 0 2 4 2 4 0
0 0 0 1 2 1 2 0
2 1 4 2
1 1
0 0 0 3 6 3 6 0
0 1 1 0 3 2 2 3
0 0 4 2
0 3

输出 #1

text

1
21.0000000000
1.2272623352

[EC Final 2022] Map

目录

形式化题目

正解

思路

代码

复杂度

总结