比赛场次 | 508 |
---|---|
比赛名称 | SYOI2022 Round2 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2022-06-15 18:30:00 |
结束时间 | 2022-06-16 21:05:00 |
开放分组 | 全部用户 |
注释介绍 |
题目名称 | Looking for Order |
---|---|
输入输出 | lenepack.in/out |
时间限制 | 5000 ms (5 s) |
内存限制 | 512 MiB |
测试点数 | 10 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
锝镆氪锂铽 | AAAAAAAAAA | 1.166 s | 133.74 MiB | 100 |
op_组撒头屯 | AAATTTTTAA | 27.929 s | 4.01 MiB | 50 |
该账号已注销 | WWWWWWWWWW | 0.000 s | 0.00 MiB | 0 |
HeSn | WWWTTTTTTT | 35.082 s | 5.74 MiB | 0 |
Lena喜欢秩序井然的生活。一天,她要去上大学了。突然,她发现整个房间乱糟糟的——她的手提包里的物品都散落在了地上。
她想把所有的物品都放回她的手提包。但是,这里有一点问题:她一次最多只能拿两个物品,她也不能移动她的手提包。
并且,因为她爱整洁的习惯,如果她拿起了一个物品,她也不能将它放在其他地方,除非放回她的手提包。
Lena把她的房间划分为了一个平面直角坐标系。现在Lena给你她的手提包和每个散落的物品的坐标(当然,一开始的时候她就和手提包站在一个地方)。
她从坐标 $(x_1,y_1)$ 走到坐标 $(x_2,y_2)$ 需要用 $(x_1-x_2)^2+(y_1-y_2)^2$ 单位的时间。
现在,Lena将告诉你她的房间的情况,请你为Lena找到一个拾起每个物品的顺序,使她拾起所有物品所需的总时间最小。当然,Lena最后需要返回她的手提包。
输入文件的第一行为Lena的手提包的坐标 $x_s$,$y_s$。
第二行为一个正整数 $n$,表示总的需要拾起的物品数。
接下来的 $n$ 行每行包括两个整数,表示每个物品的坐标。
输出一行,一个正整数,表示Lena拾起所有物品所需的最小时间。
0 0 2 1 1 -1 1
8
1 1 3 4 3 3 4 0 0
32
略。
对于 30% 的数据,$1 \le n \le 5$
对于 100% 的数据,$1 \le n \le 24$,$0 \le |x_s|,|y_s| \le 100$
翻译来自洛谷